[알고리즘 / 백준] 3055 - 탈출

www.acmicpc.net/problem/3055

3055번: 탈출

 

문제는 위와 같으며, 이 문제는 시간당 물이 이동하는 경우와 고슴도치가 이동하는 경우를 나누어 BFS 방식을 통해 고슴도치가 비버 굴로 이동하는 최소 시간을 구하면 되는 문제입니다.

 

1. 숲의 정보를 이차원 배열에 저장하고, 이때 고슴도치의 출발 위치와 물의 위치(여러 개일 수 있으므로 배열에 저장)를 각각 저장합니다.

2. BFS 메소드를 수행하여 고슴도치가 안전하게 비버 굴에 도착할 수 있는 시간을 구합니다. (도착할 수 없는 경우 -1을 반환)

    (1) 우선순위 큐를 생성하여 물 및 고슴도치가 이동할 수 있는 칸의 정보를 저장합니다.

        이때 저장하는 정보는 현재 위치로 이동하는데 걸리는 시간, 현재 칸의 정보(*, ., D, S), 현재 위치의 x, 현재 위치의 y 입니다.

        우선순위 큐는 "현재 위치로 이동하는데 걸리는 시간" 을 기준으로 우선순위를 정하고 물에 대한 정보를 고슴도치 정보보다

        먼저 추가하여 "현재 위치로 이동하는데 걸리는 시간" 이 같은 경우 물의 위치를 먼저 확인하도록 합니다.

        (같은 시간에 물이 먼저 차 있는 경우 고슴도치는 해당 위치로 이동할 수 없기 때문)

    (2) 더 이상 이동할 칸이 없을 때까지 반복하며 큐에서 데이터를 하나씩 pop 합니다.

    (3) 만약 현재 뽑은 위치가 비버 굴(도착 지점)인 경우 현재 위치까지 이동하는데 걸리는 시간을 반환합니다.

    (4) 그렇지 않은 경우, 현재 위치를 기준으로 상하좌우의 다음 위치를 구하고 다음 위치가 숲의 범위 내에 있는 경우

        - 현재 칸이 물인 경우

            - 다음 칸이 돌이 아니고 도착 지점도 아니면서 물이 아직 차지 않은 칸이라면, 다음 칸에 물이 찬 것으로 처리하고

               우선순위 큐에 다음 위치까지 이동하는데 걸린 시간, '*', 다음 위치의 x, 다음 위치의 y 데이터를 추가합니다.

        - 현재 칸이 물이 아닌 경우

            - 다음 칸이 돌이 아니고 물도 차지 않았으면서 아직 고슴도치가 이동하지 않은 칸이라면, 다음 칸으로 고슴도치가 이동한 것으로

               처리하고 우선순위 큐에 다음 위치까지 이동하는데 걸린 시간, 다음 칸의 정보(., D, S), 다음 위치의 x, 다음 위치의 y 데이터를

               추가합니다.

    (5) 더 이상 이동할 칸이 없으면서 도착 지점에 도달하지 못한 경우 -1을 반환합니다.

3. 시간이 -1 인 경우 비버 굴에 도달할 수 없으므로 "KAKTUS" 를 출력하고 그렇지 않은 경우 구한 시간을 출력합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

xx = [-1, 1, 0, 0]
yy = [0, 0, -1, 1]


def bfs():
    queue = []
    w_visited = [[False] * c for _ in range(r)]  # 물이 해당 칸에 찼는지 여부
    visited = [[False] * c for _ in range(r)]  # 고슴도치가 해당 칸으로 이동했는지 여부

	# 초기 물의 위치 및 정보를 큐에 저장하고 해당 물의 위치를 방문한 것으로 처리
    for wx, wy in water:
        heapq.heappush(queue, [0, '*', wx, wy])
        w_visited[wx][wy] = True
    heapq.heappush(queue, [0, 'S', sx, sy])  # 초기 고슴도치의 위치 및 정보를 큐에 저장하고
    visited[sx][sy] = True  # 고슴도치 시작 위치를 방문한 것으로 처리

	# 더 이상 이동할 칸이 없을 때까지 반복
    while queue:
        cnt, t, cx, cy = heapq.heappop(queue)

        # 현재 위치가 도착 위치와 같은 경우
        if t == 'D':
            return cnt  # 현재 위치까지 오는데 걸린 시간 반환

		# 상하좌우 위치를 확인하면서
        for d in range(4):
            nx = cx + xx[d]
            ny = cy + yy[d]

            if 0 <= nx < r and 0 <= ny < c:  # 다음 위치가 숲의 범위 내에 있고
                # 현재 위치가 물인 경우
                if t == '*':
                    # 다음 위치가 돌이 아니거나 도착 지점이 아니면서 아직 물이 차지 않은 경우
                    if (forest[nx][ny] != 'X' and forest[nx][ny] != 'D') and not w_visited[nx][ny]:
                        heapq.heappush(queue, [cnt + 1, '*', nx, ny])  # [물이 차는데 걸리는 시간, 물 표시, 다음 위치 x, 다음 위치 y] 데이터 저장
                        w_visited[nx][ny] = True  # 다음 위치에 물이 찼다는 것을 표시
                else:
                    # 다음 위치가 돌이 아니면서 물이 차지 않은 공간이고 아직 고슴도치가 이동하지 않은 공간인 경우
                    if (forest[nx][ny] != 'X' and not w_visited[nx][ny]) and not visited[nx][ny]:
                        heapq.heappush(queue, [cnt + 1, forest[nx][ny], nx, ny])  # [고슴도치가 다음 위치로 이동하는데 걸리는 시간, 다음 칸 정보 표시, 다음 위치 x, 다음 위치 y] 데이터 저장
                        visited[nx][ny] = True  # 다음 위치로 고슴도치가 이동한 것을 표시

    return -1  # 더 이상 이동할 칸이 없는데 비버 굴에 도달하지 못한 경우 -1을 반환


r, c = map(int, stdin.readline().split())
sx = 0
sy = 0

forest = []  # 숲의 정보 이차원 배열로 저장
water = []  # 처음 물의 위치 이차원 배열로 저장
for i in range(r):
    tmp = list(stdin.readline().strip())
    if 'S' in tmp:  # 고슴도치의 시작 위치 저장
        sx = i
        sy = tmp.index('S')

    if '*' in tmp:  # 초기 물의 위치 저장
        water.append([i, tmp.index('*')])
    forest.append(tmp)  # 숲 정보 저장

result = bfs()
if result == -1:
    print("KAKTUS")
else:
    print(result)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	// 상하좌우 이동 위치 저장
    private static int[] xx = {-1, 1, 0, 0};
    private static int[] yy = {0, 0, -1, 1};

    private static int r;
    private static int c;

    private static char[][] forest;  // 숲 정보 저장

	// 고슴도치 시작 위치 저장
    private static int sx;
    private static int sy;
    private static ArrayList<int[]> water = new ArrayList<>();  // 초기 물의 위치 저장


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        forest = new char[r][c];
        for (int i = 0; i < r; i++) {
            char[] tmp = br.readLine().toCharArray();
            for (int j = 0; j < c; j++) {
                if (tmp[j] == 'S') {  // 고슴도치 초기위치 저장
                    sx = i;
                    sy = j;
                } else if (tmp[j] == '*') {  // 초기 물의 위치 저장
                    water.add(new int[]{i, j});
                }
            }
            forest[i] = tmp;  // 숲 정보 저장
        }

        int result = bfs();
        if (result == -1) {
            System.out.println("KAKTUS");
        } else {
            System.out.println(result);
        }
    }

	// 고슴도치가 비버 굴까지 이동하는데 걸리는 최단 시간 반환 (도달하지 못하는 경우 -1 반환)
    private static int bfs() {
    	// 우선 순위 큐를 생성하여 Node 정보를 담고
        // Node 정보 중 cnt 를 기준으로 우선순위를 구하고 
        // cnt 가 같은 경우 type 을 기준으로 우선순위를 정하도록 함
        // type 은 char 형으로 아스키 값으로 비교할 때 * 이 가장 작음 (물의 위치가 앞에 와서 먼저 확인하도록 함)
        PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node node1, Node node2) {
                return node1.cnt - node2.cnt != 0 ? node1.cnt - node2.cnt : node1.type - node2.type;
            }
        });

        boolean[][] w_visited = new boolean[r][c];  // 해당 칸에 물이 찼는지 확인
        boolean[][] visited = new boolean[r][c];  // 해당 칸에 고슴도치가 이동했는지 확인

		// 초기 물의 위치를 우선순위 큐에 저장 및 해당 위치에 물이 찼다는 것을 표시
        for (int[] w : water) {
            queue.offer(new Node(0, '*', w[0], w[1]));
            w_visited[w[0]][w[1]] = true;
        }
        // 고슴도치의 출발 위치를 우선 순위 큐에 저장하고 해당 위치를 고슴도치가 방문한 것으로 표시
        queue.offer(new Node(0, 'S', sx, sy));
        visited[sx][sy] = true;

		// 더 이상 이동할 칸이 없을 때까지 반복
        while (!queue.isEmpty()) {
            Node current = queue.poll();

			// 현재 칸이 도착 칸인 경우
            if (current.type == 'D') {
                return current.cnt;  // 현재 칸까지 이동하는데 걸린 시간을 반환
            }

			// 그렇지 않은 경우, 현재 위치를 기준으로 상하좌우 위치 확인
            for (int i = 0; i < 4; i++) {
                int nx = current.x + xx[i];
                int ny = current.y + yy[i];

                if (nx >= 0 && nx < r && ny >= 0 && ny < c) {  // 다음 위치가 숲의 범위 내에 있고
                    // 현재 위치가 물인 경우
                    if (current.type == '*') {
                    	// 다음 위치가 돌이 아니고 도착지점도 아니면서 물이 아직 차지 않은 경우
                        if (forest[nx][ny] != 'X' && forest[nx][ny] != 'D' && !w_visited[nx][ny]) {
                            queue.offer(new Node(current.cnt + 1, '*', nx, ny));  // 다음 위치 정보를 우선순위 큐에 저장
                            w_visited[nx][ny] = true;  // 다음 위치에 물이 찬 것으로 처리
                        }
                    } else {
                    	// 다음 위치가 돌이 아니고 물도 차지 않았으면서 고슴도치가 이동한 적 없는 경우
                        if (forest[nx][ny] != 'X' && !w_visited[nx][ny] && !visited[nx][ny]) {
                            queue.offer(new Node(current.cnt + 1, forest[nx][ny], nx, ny));  // 다음 위치 정보를 우선순위 큐에 저장
                            visited[nx][ny] = true;  // 다음 위치에 고슴도치가 방문한 것으로 처리
                        }
                    }
                }
            }
        }

        return -1;
    }
}

// 칸의 정보 저장 클래스
class Node {
    int cnt;  // 현재 위치까지 이동하는데 걸린 시간
    char type;  // 현재 위치의 칸 정보 (*, ., D, S)
    int x;  // 현재 위치의 x
    int y;  // 현재 위치의 y

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