[백준] 3005번 - 탈출

3005번 탈출

3055번: 탈출

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

 

 

 

문제 해석해보기

이번 문제를 푸는데 어떤 알고리즘을 적용해야할지 감이 잡히시나요 ?

 

감이 잡히시지 않는다면 아래 포스팅을 읽어주세요 !!

 

[알고리즘 특강 1일차] 알고리즘이란, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 이해와 활용

 

 

 

 

 

이번 문제를 잘 읽으면 움직임에 대한 행동이 주어지는게 두 가지 있습니다.

바로 ‘고슴도치'와 ‘물'입니다.

 

고슴도치와 물이 동시에 움직이므로 BFS로 문제를 푸는 편이 훨씬 쉽습니다.

 

 

이제 문제에 대해 더 들여다 보겠습니다.

문제 요구는 다음과 같습니다.

• S(고슴도치)는 ‘.’ 혹은 ‘D(비버집)’로 움직일 수 있습니다.
• S는 ‘*’ 혹은 ‘X’로 움직일 수 없습니다.
• S가 ‘D’에 도달하면 성공입니다.
• ‘*(물)’은 상하좌우로 한 턴씩 번집니다.
• ‘*’은 ‘X’로 번질 수 없습니다.
• S는 ‘’과 함께 움직이며 다음 턴에 ‘’이 예상 될 자리에 고슴도치가 자리할 수 없습니다.

 

 

---

단계별 적용해보기

이제 BFS를 돌리기 위해서 나올 6가지 단계를 아래와 같이 주석으로 표현 해놓겠습니다.

// 1. 큐에서 꺼내옴
// 2. 목적지인가 ?
// 3. 연결된 곳 순회
	// 4. 갈 수 있는가 ?
		// 5. 체크인
		// 6. 큐에 넣음

 

이제 하나하나 이 주석에 조건들과 수행될 것들을 채워나가 봅시다.

 

먼저 이 주석을 채우기 전에 기본적으로 알고가야 할 것들이 있습니다.

• 고슴도치
  • 상하좌우로 움직인다.
  • 지도 내에 있어야 한다.
  • ‘.’에 갈 수 있고 ‘*’나 ‘X’로는 갈 수 없다.
  • ‘D’로 도착하면 성공입니다.
• 물
  • 상하좌우로 움직인다.
  • 지도 내에 있어야 한다
  • ‘X’ 혹은 ‘D’를 물로 채울 수 없습니다.

 

 

1. 큐에서 꺼내옴

먼저 BFS에서 사용할 큐(Queue)는 방문 할 예정인 곳입니다.

때문에 큐에서 꺼내올 때가 방문하는 곳이 됩니다.

저희는 고슴도치와 물이 동시에 계속 움직여줘야 합니다.

그렇다면 큐에 들어가 있는 고슴도치와 물의 위치를 계속해서 가져와서 방문 할 곳을 큐에서 poll 함으로써 알 수 있습니다.

• Point point = Q.poll();

이 때 Point는 아래 코드와 같습니다.

• 여기서 type은 * . S D X 를 표현합니다.

class Point {
	int y, x;
	char type;

	public Point(int y, int x, char type) {
		this.y = y;
		this.x = x;
		this.type = type;
	}
}

 

 

 

2. 목적지인가 ?

• 고슴도치가 ‘D’에 도달하면 성공입니다.
• 고슴도치 방문 예정은 큐에서 꺼냄으로서 알 수 있습니다.

if (point.type == 'D') {
		break;
}

 

 

 

3. 연결된 곳 순회

• 상하좌우로 움직임을 예상하여 4번에 넘겨줍니다.

 

 

4. 갈 수 있는가 ?

• 방문 할 곳이 물(*)일 경우와 고슴도치(’S’, ‘.’)일 경우로 나뉩니다.
• 이미 방문 한 곳을 다시 재방문하지 않게 중복방지를 해줘야 합니다.
• 가능 할 경우 5번으로 갑니다.

 

 

5. 체크인

• 고슴도치 일 경우
  • 방문 표시, 몇 번째 움직임인지 체크해줍니다.
• 물 일 경우
  • 지도에 .을 *로 바꿉니다.

 

6. 큐에 넣음

• 다음 방문 예정을 큐에 넣습니다.

 

 

---

BFS 코드로 구현하기

구현 시 생각해볼점

구현할 때 주의할 점이 있습니다.

요구 사항 중에

• 고슴도치는 다음에 물이 찰 곳에 갈 수 없다.

라는 조건이 존재합니다.

 

 

이 조건은 다음과 같이 생각해보면 좋습니다.

저희는 큐에 미리 고슴도치와 물을 넣어줘야 합니다.

 

고슴도치와 물이 동시에 움직임을 표현하기 위해서 입니다.

 

 

처음에 큐에 고슴도치와 물을 넣어주는 순서에 의미가 있습니다.

고슴도치 먼저 큐에 넣어줄 경우

• 고슴도치가 먼저 움직이게 됩니다.
• 고슴도치가 움직인 이후 물이 움직이는데 만약 고슴도치가 움직인 자리에 물이 온다면 ???
  • 조건에 맞지 않습니다.
  • 좀 더 복잡하게 구현을 해야 합니다

 

물 먼저 큐에 넣어줄 경우

• 물이 먼저 움직이게 됩니다.
• 물이 움직인 이후 고슴도치는 물이 없는 곳으로 움직이게 됩니다.
  • 조건에 맞습니다.
  • 물과 고슴도치의 순서만 바꿔줘도 해결이 가능합니다.

 

몇 번만에 성공했는지 어떻게 알 수 있을까 ?? // 방문 중복 방지

• int 타입의 2차원 배열을 초기화하여 사용하면 됩니다.
• 고슴도치의 첫 위치 값을 0이라고 하면 다음 상하좌우는 0 + 1 이 됩니다.
• 또한 방문 중복 방지를 판단하기 위해서는 다음과 같은 코드를 사용할 수 있습니다.

int[][] count = int[N][K];

// 상하좌우 움직인 (ny, nx) 좌표
if (count[ny][nx] == 0) {
	// 0이므로 아직 방문하지 않음
}

 

 

 

 

이제 구현하면 아래와 같은 코드가 나오게 됩니다.

package 백준.자바_특강.DAY1.탈출;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point {
    int y, x;
    char type;

    public Point (int y, int x, char type) {
        this.y = y;
        this.x = x;
        this.type = type;
    }
}
public class Main {

    static final int[] dy = {1, -1, 0, 0};
    static final int[] dx = {0, 0, 1, -1};

    static int N, M;
    static char[][] map;
    static int[][] turnCount;
    static Queue<Point> Q;
    static boolean foundAnswer;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new char[N][M];
        turnCount = new int[N][M];
        Q = new LinkedList<>();

        Point st = null;
        for (int y = 0; y < N; y++) {
            String line = sc.next();
            for (int x = 0; x < M; x++) {
                map[y][x] = line.charAt(x);
                if (map[y][x] == '*') {
                    Q.add(new Point(y, x, '*'));
                } else if (map[y][x] == 'S') {
                    st = new Point(y, x, 'S');
                }
            }
        }
        Q.add(st);

        while (!Q.isEmpty()) {
            // 1. 큐에서 꺼내옴
            Point point = Q.poll();

            // 2. 목적지 인가 ? -> D
            if (point.type == 'D') {
                System.out.println(turnCount[point.y][point.x]);
                foundAnswer = true;
                break;
            }

            // 3. 연결된 곳 순회
            for (int i = 0; i < 4; i++) {
                int ny = point.y + dy[i];
                int nx = point.x + dx[i];

                // 4. 갈 수 있는가 ?
                if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                    if (point.type == 'S' || point.type == '.') {
                        // 4. 고슴도치 : D, 방문하지 않은 곳(.)
                        if ((map[ny][nx] == '.' || map[ny][nx] == 'D') && turnCount[ny][nx] == 0) {
                            // 5. 체크인
                            turnCount[ny][nx] = turnCount[point.y][point.x] + 1;
                            // 6. 큐에 넣음
                            Q.add(new Point(ny, nx, map[ny][nx]));
                        }
                    } else if (point.type == '*') {
                        // 4. 물 : ., S
                        if (map[ny][nx] == '.' || map[ny][nx] == 'S') {
                            // 5. 체크인
                            map[ny][nx] = '*';
                            // 6. 큐에 넣음
                            Q.add(new Point(ny, nx, '*'));
                        }
                    }
                }
            }

        }

        if (!foundAnswer) {
            System.out.println("KAKTUS");
        }
    }

}