백준 1938번: 통나무 옮기기

문제 설명

• https://www.acmicpc.net/problem/1938
• 3칸을 차지하는 통나무를 4방으로 이동하거나 회전하는 과정을 몇 번 거쳐 목적지에 도달하는지 계산하는 문제입니다.

접근법

• 통나무의 중심을 기준으로 값을 확인하는 방식으로 문제를 풀었습니다.

• 통나무의 이동은 4방향이지만 통나무의 상태가 가로냐 아니면 세로냐에 따라 확인해야 할 값이 달라집니다.

  • 
  • 
  • 
  • 

• 통나무의 회전은 다음 조건을 만족해야 합니다.

  • 중심을 기준으로 3x3공간이 확보되어 있어야 합니다.
  • 중심을 기준으로 확보한 3x3공간에 1(나무)이 없어야 합니다.

• 가로로 방문한 공간을 세로로도 방문할 수 있어야 합니다.

  • 회전은 좌표위치를 바꾸지 않기 때문에 이전 방문처리의 영향을 받지 않아야 합니다.
    저는 3차원 방문배열을 사용해 같은 공간을 가로로 방문했는지와 세로로 방문했는지를 다르게 구분했습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		char[][] board = new char[N][N];
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}
		int[] center = findCenter(board, 'B');
		int[] goal = findCenter(board, 'E');
		System.out.println(BFS(board, center, goal));
	}

	// 나무의 중심 찾기
	public static int[] findCenter(char[][] board, char symbol) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] == symbol) {
					if (j + 1 < N && board[i][j + 1] == symbol) { // BBB
						return new int[] { i, j + 1, 0 };
					} else {
						return new int[] { i + 1, j, 1 };
					}
				}
			}
		}
		return new int[] {};
	}

	// BFS
	public static int BFS(char[][] board, int[] center, int[] goal) {
		boolean[][][] visited = new boolean[N][N][2]; // 가로로 방문하는 것과 세로로 방문하는 것이 다르기 때문에 3차원으로 구현해야 합니다.
		visited[center[0]][center[1]][center[2]] = true;
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(center);
		int cnt = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			while (--size >= 0) {
				int[] now = q.poll();
				if (now[0] == goal[0] && now[1] == goal[1] && now[2] == goal[2]) {

					return cnt;
				}

				List<int[]> moveList = canMoveList(board, now);
				for (int i = 0; i < moveList.size(); i++) {
					int[] next = moveList.get(i);
					if (visited[next[0]][next[1]][next[2]])
						continue;
					visited[next[0]][next[1]][next[2]] = true;
					q.add(next);
				}
			}
			cnt++;
		}
		return 0;
	}

	public static List<int[]> canMoveList(char[][] board, int[] now) {
		List<int[]> list = new LinkedList<int[]>();
		int r, c, d;
		d = now[2];
		// 앞
		r = now[0];
		c = now[1] + 1;
		if (d == 0) {
			if (c + 1 < N && board[r][c + 1] != '1') {
				list.add(new int[] { r, c, d });
			}
		} else {
			if (c < N && 0 <= r - 1 && r + 1 < N && board[r - 1][c] != '1' && board[r][c] != '1'
					&& board[r + 1][c] != '1') {
				list.add(new int[] { r, c, d });
			}
		}
		// 뒤
		r = now[0];
		c = now[1] - 1;
		if (d == 0) {
			if (0 <= c - 1 && board[r][c - 1] != '1') {
				list.add(new int[] { r, c, d });
			}
		} else {
			if (0 <= c && 0 <= r - 1 && r + 1 < N && board[r - 1][c] != '1' && board[r][c] != '1'
					&& board[r + 1][c] != '1') {
				list.add(new int[] { r, c, d });
			}
		}
		// 위
		r = now[0] - 1;
		c = now[1];
		if (d == 0) {
			if (0 <= r && 0 <= c - 1 && c + 1 < N && board[r][c - 1] != '1' && board[r][c] != '1'
					&& board[r][c + 1] != '1') {
				list.add(new int[] { r, c, d });
			}
		} else {
			if (0 <= r - 1 && board[r - 1][c] != '1') {
				list.add(new int[] { r, c, d });
			}
		}
		// 아래
		r = now[0] + 1;
		c = now[1];
		if (d == 0) {
			if (r < N && 0 <= c - 1 && c + 1 < N && board[r][c - 1] != '1' && board[r][c] != '1'
					&& board[r][c + 1] != '1') {
				list.add(new int[] { r, c, d });
			}
		} else {
			if (r + 1 < N && board[r + 1][c] != '1') {
				list.add(new int[] { r, c, d });
			}
		}
		// 회전
		r = now[0];
		c = now[1];
		boolean flag = true;
		if (0 > r - 1 || r + 1 >= N || 0 > c - 1 || c + 1 >= N) { // 3x3공간을 확보하지 못하면 회전할 수 없습니다.
			flag = false;
		}
		for (int i = r - 1; i <= r + 1; i++) {
			for (int j = c - 1; j <= c + 1; j++) {
				if (0 <= i && i < N && 0 <= j && j < N && board[i][j] == '1') { // 3x3공간에 1이 존재하면 회전할 수 없습니다.
					flag = false;
				}
			}
		}
		if (flag) {
			list.add(new int[] { r, c, Math.abs(d - 1) });
		}
		return list;
	}

}