[백준] 1600번: 말이 되고픈 원숭이 - java

 

 

나의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static StringBuilder sb;
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int k, w, h;
	static int[][] map;
	static boolean[][][] visited;
	static int first_row = -1;
	static int first_col = -1;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int[] horse_dx = { -2, -2, -1, -1, 1, 1, 2, 2 };
	static int[] horse_dy = { -1, 1, -2, 2, -2, 2, -1, 1 };

	public static void main(String[] args) throws IOException {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();
		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		map = new int[h][w];
		visited = new boolean[h][w][k+1]; // 지금까지 말을 k번 움직였을 때 (i,j) 방문 여부
		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < w; j++) {
				map[i][j] = Integer.parseInt(st.nextToken()); // 0은 평지, 1은 장애물
			}
		}
		sb.append(bfs());

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static int bfs() {
		Queue<int[]> q = new ArrayDeque<int[]>();
		q.add(new int[] { 0, 0, 0, 0 }); // x좌표, y좌표, 말처럼 움직인횟수, 총 움직인횟수
		visited[0][0][0] = true;

		while (!q.isEmpty()) {
			int[] info = q.poll();
			int x = info[0];
			int y = info[1];
			int horse_cnt = info[2];
			int cnt = info[3];
			
			if (x == h - 1 && y == w- 1) {
				return cnt;
			}

			if (horse_cnt < k) {
				// 말의 움직임으로 움직이기
				for (int i = 0; i < 8; i++) {
					int nx = x + horse_dx[i];
					int ny = y + horse_dy[i];
					if (nx >= 0 && nx < h && ny >= 0 && ny < w && map[nx][ny] != 1 && !visited[nx][ny][horse_cnt+1]) {
						visited[nx][ny][horse_cnt+1] = true;
                        q.add(new int[] { nx, ny, horse_cnt+1, cnt + 1 });
					}
				}
			}

			// 인접한 네 방향으로 움직이기
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < h && ny >= 0 && ny < w && map[nx][ny] != 1 && !visited[nx][ny][horse_cnt]) {
					visited[nx][ny][horse_cnt] = true;
					q.add(new int[] { nx, ny, horse_cnt, cnt + 1 });
				}
			}

		}
		return -1;
	}
}

 

단순한 BFS 같아보이지만,,, ! 함정이 있는 문제다.

 

기존의 BFS 처럼, visited[i][j] 만 검사하고, 이미 방문한 경우에는 해당 노드를 더이상 탐색하지 않는다고 가정해보자.

이때, 아래 입력이 들어왔다면, 어떻게 될까?

말의 움직임으로 이동할 수 있는 경우는 오직 1번 뿐이다.

1
4 4
0 0 1 1
1 0 1 1
1 0 1 1
1 1 1 0

 

<1번째 턴>

현재 노드는 (0,0) 이다.

먼저, 말의 움직임으로 (2,0) 노드에 도달했다. 더 이상 말의 움직임으로 도달할 수 있는 경우는 없다.

 

인접한 상하좌우를 탐색하자.

(0,1) 노드에 도달했다. 

Queue : (2,0) , (0,1)

 

 

<2번째 턴>

현재 노드는 (2,0) 이다. 이미 말의 움직임으로 1번 이동했기에, 더 이상 말의 움직임을 탐색할 필요가 없다.

 

인접한 상하좌우를 탐색하자.

(1,1) 노드에 도달했다.

Queue : (0,1), (1,1)

 

 

<3번째 턴>

현재 노드는 (0,1) 이다. 누적된 말의 움직임은 0번이지만, 말의 움직임으로 이동할 수 있는 노드가 없다.

 

인접한 상하좌우를 탐색하자.

(1,1) 노드는 이미 방문처리되었기에, 처리할 수 없다. => 문제가 된다!!!!

위 경우 (0,0)->(0,1)->(1,1)->(2,1)->(3,3) 으로 총 4번의 이동이 정답이다.

 

그러나, visited[i][j] 로 방문처리를 한다면, 

(i,j) 노드를 방문하기까지 이동한 말의 움직임 횟수를 고려하지 않게 된다.

만약, 이미 k번의 말의 움직임을 다 사용하고 (i,j) 에 도착한 경우, (i,j) 에서 더 이상 말의 움직임을 탐색할 수 없다.

그러나, 다른 노드에서 아직 k번의 말의 움직임을 다 사용하지 않은 경우에 (i,j) 에 도착한다면, (i,j) 에서 말의 움직임으로 탐색할 수 있으므로, 이 경우는 이미 해당 노드를 방문했더라도 다른 결과를 초래하게 된다.

 

따라서 오직 (i,j) 좌표를 방문한 적이 있냐로 탐색여부를 확인하는 것이 아니라,

(i,j) 노드를 방문하기까지 이동한 말의 움직임 횟수가 같은지까지 확인하는 과정이 필요하다.

이를 위해 visited = new boolean[h][w][k + 1] 로 지금까지 움직인 말의 움직임 횟수까지 비교해주도록 하였다.

 

 

나머지는 기존의 BFS 구현과 동일하다.

visited[] 로 말의 움직임 횟수까지 비교해주는 것이 관건이다 >-<

 

위와 같이, 현재 노드까지 사용한 말의 움직임 횟수가 K보다 작다면, 말의 움직임 + 인접한 네 방향을 탐색하고,

그렇지 않다면, 인접한 네 방향으로만 움직이게 한다.

 

말의 움직임으로 이동한 경우라면 아래와 같이 horse_cnt 를 1추가해준다.

 

노드가 끝에 도달했다면, 총 움직임 횟수 cnt 를 반환해준다.