백준 1938번 : 통나무 옮기기 [Java]

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

문제 탐색하기

전형적인 bfs 문제에서 약간의 변형을 한 느낌의 문제이다. 이전에 프로그래머스에서도 비슷한 카카오 문제를 본적이 있는 것 같은데 그 때의 경험을 되살려보며 생각해보자. 길이가 3인 통나무를 주어진 방식대로 옮기려면 동시에 3칸을 고려해야한다. 또한 방향이 가로 또는 세로로 들어갈 수 있으므로 2가지 방향에 대한 방문을 기록해두고 너비 우선 탐색을 진행하면 답을 구할 수 있을 것이다.

 

회전은 중심축을 기준으로 현재 통나무가 없는 방향들을 확인하면 되는데, 이 때 중간에 하나라도 다른 나무이거나 범위를 벗어난것이 있다면 회전이 불가하니 알아두자. 답을 출력할 때는 원본 지도에 나와 있는 도착지점의 좌표와 통나무의 방향을 미리 계산해두고 해당 좌표만 출력하면 답을 받을 수 있다.

 

코드 구현하기

1. 입력을 처리하고 방문과 동시에 동작 횟수를 기록할 3차원 배열을 만든다.
2. 입력을 처리할 때 도착 지점의 중간 점의 좌표와 방향, 시작 통나무의 중간 점의 좌표와 방향을 모두 기록한다.
3. 너비 우선 탐색을 통해서 모든 지점을 탐사한다. 이때 특정 방향으로 접근한적이 있는지를 이전에 만들어둔 3차원 배열을 통해서 확인할 수 있다.
4. 앞서 구한 도착지점의 중간 점의 좌표와 방향을 통해서 답을 출력한다.

시도 회차 수정 사항

1회차

통나무 클래스를 만들고 이것저것 잔뜩 집어넣고 bfs를 구현했더니 메모리 초과를 받았다. 메모리 압축을 위해서 통나무의 모든 좌표를 추적하지 않고 구할 방법을 찾다가 중간 점의 좌표만으로도 매번 연산을 통해서 확인해야 될 부분만 확인하고 넘길 수 있다는 사실을 알게되어서 수정하였다.

 

또한 클래스의 인스턴스보다 배열이 메모리를 덜 잡아먹으므로 int[] 배열을 통해서 bfs를 하도록 구현하였다.

 

2회차

기껏 수정했지만 통나무의 방향이 틀리게 계산되는걸 보고 왜맞틀? 이었다. 좌표값을 확인해보니 i를 두 번 빼고 있어서 생긴 일이었다. 이에 따라서 수정하여 정답을 받을 수 있었다.

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static int N, ansCount = 0, ax, ay, aDir, sCount = 0, sx, sy, sDir;
	static char[][] map;
	static int[][][] answer;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		map = new char[N][N];
		answer = new int[N][N][2];
		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < N; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'B' && sCount < 2) {
					if (sCount == 1) {
						if (Math.abs(i - sx) == 1) {
							sDir = 0;
						} else if (Math.abs(j - sy) == 1) {
							sDir = 1;
						}
					}
					sx = i;
					sy = j;
					sCount++;
				} else if (map[i][j] == 'E' && ansCount < 2) {
					if (ansCount == 1) {
						if (Math.abs(i - ax) == 1) {
							aDir = 0;
						} else if (Math.abs(j - ay) == 1) {
							aDir = 1;
						}
					}
					ax = i;
					ay = j;
					ansCount++;
				}
			}
		}

		bfs();
		System.out.println(answer[ax][ay][aDir]);
	}

	private static void bfs() {
		LinkedList<int[]> q = new LinkedList<>();
		answer[sx][sy][sDir] = -1;
		q.add(new int[] {sx, sy, sDir, 0});
		while (!q.isEmpty()) {
			int[] now = q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = now[0];
				int ny = now[1];
				// 세로
				if (now[2] == 0) {
					if (i < 2) {
						nx += dx[i];
						ny += dy[i];
						if (answer[nx][ny][now[2]] != 0) {
							continue;
						}
						nx += dx[i];
						ny += dy[i];
						if (isOutOfBounds(nx, ny) || map[nx][ny] == '1') {
							continue;
						}
						nx -= dx[i];
						ny -= dy[i];
						q.add(new int[] {nx, ny, now[2], now[3] + 1});
						answer[nx][ny][now[2]] = now[3] + 1;
					} else {
						int upX = nx + dx[0] + dx[i];
						int upY = ny + dy[0] + dy[i];
						int downX = nx + dx[1] + dx[i];
						int downY = ny + dy[1] + dy[i];
						nx += dx[i];
						ny += dy[i];
						if (isOutOfBounds(nx, ny) || isOutOfBounds(upX, upY) || isOutOfBounds(downX, downY)
							|| answer[nx][ny][now[2]] != 0 || map[nx][ny] == '1' || map[upX][upY] == '1'
							|| map[downX][downY] == '1') {
							continue;
						}
						q.add(new int[] {nx, ny, now[2], now[3] + 1});
						answer[nx][ny][now[2]] = now[3] + 1;
					}
				} else {
					if (i >= 2) {
						nx += dx[i];
						ny += dy[i];
						if (answer[nx][ny][now[2]] != 0) {
							continue;
						}
						nx += dx[i];
						ny += dy[i];
						if (isOutOfBounds(nx, ny) || map[nx][ny] == '1') {
							continue;
						}
						nx -= dx[i];
						ny -= dy[i];
						q.add(new int[] {nx, ny, now[2], now[3] + 1});
						answer[nx][ny][now[2]] = now[3] + 1;
					} else {
						int leftX = nx + dx[2] + dx[i];
						int leftY = ny + dy[2] + dy[i];
						int rightX = nx + dx[3] + dx[i];
						int rightY = ny + dy[3] + dy[i];
						nx += dx[i];
						ny += dy[i];
						if (isOutOfBounds(nx, ny) || isOutOfBounds(leftX, leftY) || isOutOfBounds(rightX, rightY)
							|| answer[nx][ny][now[2]] != 0 || map[nx][ny] == '1' || map[leftX][leftY] == '1'
							|| map[rightX][rightY] == '1') {
							continue;
						}
						q.add(new int[] {nx, ny, now[2], now[3] + 1});
						answer[nx][ny][now[2]] = now[3] + 1;
					}
				}
			}

			int nx = now[0];
			int ny = now[1];

			if (now[2] == 0) {
				int upLeftX = nx + dx[0] + dx[2];
				int upLeftY = ny + dy[0] + dy[2];
				int midLeftX = nx + dx[2];
				int midLeftY = ny + dy[2];
				int downLeftX = nx + dx[1] + dx[2];
				int downLeftY = ny + dy[1] + dy[2];
				int upRightX = nx + dx[0] + dx[3];
				int upRightY = ny + dy[0] + dy[3];
				int midRightX = nx + dx[3];
				int midRightY = ny + dy[3];
				int downRightX = nx + dx[1] + dx[3];
				int downRightY = ny + dy[1] + dy[3];
				if (isOutOfBounds(upLeftX, upLeftY) || isOutOfBounds(midLeftX, midLeftY)
					|| isOutOfBounds(downLeftX, downLeftY)
					|| isOutOfBounds(midRightX, midRightY) || isOutOfBounds(upRightX, upRightY) || isOutOfBounds(
					downRightX, downRightY) || map[upLeftX][upLeftY] == '1' || map[midLeftX][midLeftY] == '1'
					|| map[downLeftX][downLeftY] == '1' || map[upRightX][upRightY] == '1'
					|| map[midRightX][midRightY] == '1' || map[downRightX][downRightY] == '1'
					|| answer[nx][ny][1 - now[2]] != 0) {
					continue;
				}
				q.add(new int[] {nx, ny, 1 - now[2], now[3] + 1});
				answer[nx][ny][1 - now[2]] = now[3] + 1;
			} else {
				int leftUpX = nx + dx[2] + dx[0];
				int leftUpY = ny + dy[2] + dy[0];
				int midUpX = nx + dx[0];
				int midUpY = ny + dy[0];
				int rightUpX = nx + dx[3] + dx[0];
				int rightUpY = ny + dy[3] + dy[0];
				int leftDownX = nx + dx[2] + dx[1];
				int leftDownY = ny + dy[2] + dy[1];
				int midDownX = nx + dx[1];
				int midDownY = ny + dy[1];
				int rightDownX = nx + dx[3] + dx[1];
				int rightDownY = ny + dy[3] + dy[1];
				if (isOutOfBounds(leftUpX, leftUpY) || isOutOfBounds(midUpX, midUpY) || isOutOfBounds(rightUpX,
					rightUpY) || isOutOfBounds(leftDownX, leftDownY) || isOutOfBounds(midDownX,
					midDownY) || isOutOfBounds(rightDownX, rightDownY) || map[leftUpX][leftUpY] == '1'
					|| map[midUpX][midUpY] == '1' || map[rightUpX][rightUpY] == '1' || map[leftDownX][leftDownY] == '1'
					|| map[midDownX][midDownY] == '1' || map[rightDownX][rightDownY] == '1' || answer[nx][ny][1 - now[2]] != 0) {
					continue;
				}
				q.add(new int[] {nx, ny, 1 - now[2], now[3] + 1});
				answer[nx][ny][1 - now[2]] = now[3] + 1;
			}
		}
	}

	static boolean isOutOfBounds(int x, int y) {
		return x < 0 || x >= N || y < 0 || y >= N;
	}

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}