[JAVA] BOJ_3055. 탈출

🐒 문제

3055번: 탈출

---

🦍 풀이

핵심 : BFS 알고리즘을 통해 물, 고슴도치를 퍼뜨리며 고슴도치가 땅굴에 도달할 수 있는지를 구현

 

1. 매 턴마다 물을 먼저 퍼뜨리고, 그 다음 고슴도치를 이동시켜야 한다.
 => 맵을 입력받고 생성하는 과정에서 고슴도치의 위치, 물의 위치를 저장시켜준다.

map = new char[R][C];

for (int i = 0; i < R; i++) {

    // 한 줄 입력받고
    String input = br.readLine();
    for (int j = 0; j < C; j++) {

        // 각 좌표에 입력받은 값들 넣어주기
        map[i][j] = input.charAt(j);

        // 고슴도치의 위치를 입력받았다면
        if (map[i][j] == 'S') {

            // 고슴 도치의 위치(시작 위치)를 따로 저장해둔다
            start = new int[] { i, j };

            // 물의 위치를 입력받았다면
        } else if (map[i][j] == '*') {

            // 큐에 물의 위치들을 넣어준다
            waters.add(new int[] { i, j });  // waters : Queue<int[]>
        }
    }
}

 

2. BFS 메서드를 작성하는 과정에서, 저장된 물의 방문을 먼저 처리하고 그 다음 고슴도치의 방문을 처리한다.

Queue<int[]> queue = new LinkedList<>();
visited = new int[R][C];

// 물을 먼저 퍼뜨려야하므로 물을 저장한 큐(waters)에서 물을 꺼내 큐에 넣어준다
while (!waters.isEmpty()) {
    int[] water = waters.poll();
    queue.add(water);
}

// 고슴도치를 큐에 넣어준다.
queue.add(start);

 

3. BFS 내부에서 이동하는 횟수를 기록해야 하는데, 이를 2차원 배열을 통해 처리하였다.

// 4방 탐색
for (int i = 0; i < 4; i++) {
    int nr = now[0] + dr[i];
    int nc = now[1] + dc[i];

    // 다음 좌표의 유효성 검사
    if (nr >= 0 && nc >= 0 && nr < R && nc < C) {

        // 다음 좌표가 이동 가능한 땅이라면
        if (map[nr][nc] == '.') {

            // 해당 위치로 'S' 또는 '*'를 퍼뜨려준다.
            map[nr][nc] = map[now[0]][now[1]];

            // 이동한 횟수를 1 늘려 저장해준다.
            visited[nr][nc] = visited[now[0]][now[1]] + 1;

            // 다음 좌표를 큐에 넣어준다.
            queue.add(new int[] { nr, nc });

            // 현재 고슴도치를 이동할 차례에서 다음으로 이동할 좌표가 땅굴이라면
        } else if (map[nr][nc] == 'D' && map[now[0]][now[1]] == 'S') {

            // 현재 위치까지 온 이동횟수에 1을 더해 출력한 후
            System.out.println(visited[now[0]][now[1]] + 1);

            // 시스템 종료
            System.exit(0);
        }
    }
}

---

🐕‍🦺 소스 코드

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

public class Main {
	static int R, C;
	static char[][] map;
	static int[][] visited;
	static int[] start;
	static Queue<int[]> waters = new LinkedList<>();

	// 델타 배열
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		// 행, 열 입력
		R = Integer.parseInt(st.nextToken(" "));
		C = Integer.parseInt(st.nextToken(" "));

		// 2차원 배열 map 선언
		map = new char[R][C];

		for (int i = 0; i < R; i++) {

			// 한 줄 입력받고
			String input = br.readLine();
			for (int j = 0; j < C; j++) {

				// 각 좌표에 입력받은 값들 넣어주기
				map[i][j] = input.charAt(j);

				// 고슴도치의 위치를 입력받았다면
				if (map[i][j] == 'S') {

					// 고슴 도치의 위치(시작 위치)를 따로 저장해둔다
					start = new int[] { i, j };

					// 물의 위치를 입력받았다면
				} else if (map[i][j] == '*') {

					// 큐에다 물의 위치들을 넣어준다
					waters.add(new int[] { i, j });
				}
			}
		}

		BFS();

		// 시스템이 종료되지 않고 BFS가 끝까지 돌았다면 고슴도치가 땅굴에 도착하지 못한 것이므로
		// KAKTUS를 출력한다.
		System.out.println("KAKTUS");

	}

	public static void BFS() {
		Queue<int[]> queue = new LinkedList<>();
		visited = new int[R][C];

		// 물을 먼저 퍼뜨려야하므로 물을 저장한 큐(waters)에서 물을 꺼내 큐에 넣어준다
		while (!waters.isEmpty()) {
			int[] water = waters.poll();
			queue.add(water);
		}

		// 고슴도치를 큐에 넣어준다.
		queue.add(start);

		while (!queue.isEmpty()) {
			int[] now = queue.poll();

			// 4방 탐색
			for (int i = 0; i < 4; i++) {
				int nr = now[0] + dr[i];
				int nc = now[1] + dc[i];

				// 다음 좌표의 유효성 검사
				if (nr >= 0 && nc >= 0 && nr < R && nc < C) {

					// 다음 좌표가 이동 가능한 땅이라면
					if (map[nr][nc] == '.') {

						// 해당 위치로 'S' 또는 '*'를 퍼뜨려준다.
						map[nr][nc] = map[now[0]][now[1]];

						// 이동한 횟수를 1 늘려 저장해준다.
						visited[nr][nc] = visited[now[0]][now[1]] + 1;

						// 다음 좌표를 큐에 넣어준다.
						queue.add(new int[] { nr, nc });

						// 현재 고슴도치를 이동할 차례에서 다음으로 이동할 좌표가 땅굴이라면
					} else if (map[nr][nc] == 'D' && map[now[0]][now[1]] == 'S') {

						// 현재 위치까지 온 이동횟수에 1을 더해 출력한 후
						System.out.println(visited[now[0]][now[1]] + 1);

						// 시스템 종료
						System.exit(0);
					}
				}
			}
		}
	}
}

🐖 Think

- 문제에 명시는 되어있지만, 물을 먼저 퍼뜨리고 그 다음에 고슴도치를 움직이는 점을 구현하는 것이 이런 문제에 익숙치 않다면 조금 헤맬 수 있을 것 같았다.