[알고리즘][X] 통나무 옮기기

https://www.acmicpc.net/problem/1938

1938번: 통나무 옮기기

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


public class Main {
	static class Train {
		Point point;
		int dir;
		int count;
		public Train(Point point, int dir, int count) {
			super();
			this.point = point;
			this.dir = dir;
			this.count = count;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][N];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		
		List<Point> pointB = new ArrayList<>();
		List<Point> pointE = new ArrayList<>();
		for (int i = 0; i < N; i++	) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 'B') {
					pointB.add(new Point(i, j));
				} else if (map[i][j] == 'E') {
					pointE.add(new Point(i, j));
				}
			}
		}
		
		Point b = pointB.get(1);
		Point e = pointE.get(1);
		
		int dirB;
		if (pointB.get(0).x == pointB.get(1).x) {
			dirB = 1;
		} else {
			dirB = 0;
		}
		int dirE;
		if (pointE.get(0).x == pointE.get(1).x) {
			// 가로
			dirE = 1;
		} else {
			// 세로
			dirE = 0;
		}
		
		Train trainB = new Train(b, dirB, 0);
		Train trainE = new Train(e, dirE, 0);
		
		Deque<Train> deque = new ArrayDeque<>();
		deque.add(trainB);
		boolean[][][] visited = new boolean[N][N][2];
		visited[trainB.point.x][trainB.point.y][trainB.dir] = true;
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		while (!deque.isEmpty()) {
			Train train = deque.poll();
			int x = train.point.x;
			int y = train.point.y;
			int dir = train.dir;
			int count = train.count;
			if (x == trainE.point.x && y == trainE.point.y && dir == trainE.dir) {
				System.out.println(count);
				return;
			}
			int nx = x;
			int ny = y;
			for (int i = 0; i <5; i++) {
				if (i != 4) {
					nx = x + dx[i];
					ny = y + dy[i];
				
				if (dir == 0) {
					if (!(0 <= nx - 1 && nx + 1 < N && 0 <= ny && ny < N)) {
						continue;
					}
					if (!(map[nx][ny] != '1' && map[nx-1][ny] != '1' && map[nx+1][ny] != '1')) {
						continue;
					}
					if (visited[nx][ny][dir]) {
						continue;
					}
					visited[nx][ny][dir] = true;
					deque.add(new Train(new Point(nx, ny), dir, count + 1));
				} else {
					if (!(0 <= ny - 1 && ny + 1 < N && 0 <= nx && nx < N)) {
						continue;
					}
					if (!(map[nx][ny] != '1' && map[nx][ny-1] != '1' && map[nx][ny+1] != '1')) {
						continue;
					}
					if (visited[nx][ny][dir]) {
						continue;
					}
					visited[nx][ny][dir] = true;
					deque.add(new Train(new Point(nx, ny), dir, count + 1));
				}
				
				}
				
				else {
					if (!(0 <= x - 1 && x + 1 < N && 0 <= y - 1 && y + 1 < N)) {
						continue;
					}
					int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
					int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
					
					boolean flag = true;
					for (int k = 0; k < 8; k++) {
						nx = x + dr[k];
						ny = y + dc[k];
						if (map[nx][ny] == '1') {
							flag = false;
							break;
						}
					}
					
					if (!flag) {
						continue;
					}
					
					int ndir = 1 - dir;
					if (visited[x][y][ndir]) {
						continue;
					}
					
					visited[x][y][ndir] = true;
					deque.add(new Train(new Point(x, y), ndir, count + 1));
				}
			}
		}
		System.out.println(0);
	}
}

나의 풀이

- deque에 넣어줄때 count+1를 해주어야 하는데 count++를 해주었다. 이렇게 되면 count 값 자체가 증가하기 때문에 다음 순회에 영향을 주게 된다. 조심하자!!!