[알고리즘 / 백준] 2206 - 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

문제는 위와 같으며, 일반적인 BFS 문제에 벽을 부수는 경우가 추가된 것입니다.

 

따라서 단순히 해당 위치를 방문했는지 여부를 확인하는 visited 배열을 [0, 0] 으로 만들어서 [벽을 부수지 않고 해당 위치를 방문한 경우 지나온 칸 수, 벽을 부수고 해당 위치를 방문한 경우 지나온 칸 수] 를 저장하는 형태로 생성합니다.

 

그리고 큐에 데이터를 저장할 때 [현재 위치의 x, 현재 위치의 y, 부수고 지나온 벽의 수] 와 같은 형태로 데이터를 저장합니다.

 

이후 큐에 데이터가 없을 때까지 반복하면서

1. 다음 위치가 벽이면서 아직 벽을 부수고 오지 않았다면, 이 경우는 다음 위치 벽을 부수고 이동할 수 있도록 visited 배열을 업데이트 해줍니다.

2. 다음 위치가 벽이 아니고 아직 다음 위치에 방문하지 않은 경우 또한 다음 위치로 이동할 수 있기 때문에 그에 맞게 visited 배열을 업데이트 해줍니다.

 

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

from sys import stdin
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    queue = deque()
    queue.append([0, 0, 0])  # [현 위치 x, 현 위치 y, 부수고 온 벽의 수] 를 BFS 를 수행할 큐에 저장

    # 각 위치의 방문 여부 및 지나온 벽 수를 저장하는데 [벽을 부수지 않고 방문한 경우, 벽을 부수고 방문한 경우] 형태로 저장
    visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    visited[0][0][0] = 1  # 초기 위치인 (0, 0)의 경우 벽을 부수지 않고 방문한 경우가 초기값이므로 1 저장

    while queue:
        cx, cy, break_count = queue.popleft()

        # 도착 지점에 도달한 경우
        if cx == n - 1 and cy == m - 1:
            return visited[cx][cy][break_count]  # 현 위치에서 벽을 부수고 방문한 경우 및 벽을 부수지 않고 방문한 경우 중 먼저 도달한 경우를 반환

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

            if 0 <= nx < n and 0 <= ny < m:  # 다음 위치가 범위 내에 존재하고
                if maze[nx][ny] == 1 and break_count == 0:  # 다음 위치가 벽인데 아직 벽을 부수고 오지 않은 경우
                    visited[nx][ny][1] = visited[cx][cy][0] + 1  # 다음 위치의 벽을 부수고 온 경우는 현 위치의 벽을 부수고 오지 않은 경우 +1 저장
                    queue.append([nx, ny, 1])  # 다음 위치 저장 및 부술 벽이 없으므로 0을 저장

                if maze[nx][ny] == 0 and visited[nx][ny][break_count] == 0:  # 다음 위치가 빈 공간이고 아직 방문하지 않은 경우
                    visited[nx][ny][break_count] = visited[cx][cy][break_count] + 1  # 다음 위치를 방문하는데 지나온 칸 수 저장
                    queue.append([nx, ny, break_count])  # 다음 위치 및 이전 위치의 벽을 부순 수를 그대로 저장

    return -1


n, m = map(int, stdin.readline().split())
maze = []
for _ in range(n):
    maze.append(list(map(int, stdin.readline().strip())))

print(bfs())

 

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class BJAlgo_2206 {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    private static int n;
    private static int m;

    private static int[][] maze;

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

        maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            maze[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        }

        System.out.println(bfs());
    }

    private static int bfs() {
        Deque<Node> deque = new ArrayDeque();
        deque.add(new Node(0, 0, 0));

		// 각 위치를 방문할 때까지 지나온 칸의 수를 저장하는데, [벽을 부수지 않고 지나온 경우, 벽을 부수고 지나온 경우] 형태로 저장
        int[][][] visited = new int[n][m][2];
        visited[0][0][0] = 1;

        while (!deque.isEmpty()) {
            Node current = deque.pollFirst();

			// 도착 지점에 도달한 경우
            if (current.x == n - 1 && current.y == m - 1) {
                return visited[current.x][current.y][current.breakCount];  // 현 위치까지 이동하는데 부수고 온 벽의 수 반환
            }

			// 다음 위치를 확인하고
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                	// 다음 위치가 빈 공간이면서 아직 방문하지 않은 경우
                    if (maze[nx][ny] == 0 && visited[nx][ny][current.breakCount] == 0) {
                        visited[nx][ny][current.breakCount] = visited[current.x][current.y][current.breakCount] + 1;
                        deque.add(new Node(nx, ny, current.breakCount));
                    }

					// 다음 위치가 벽이면서 아직 벽을 부수고 오지 않은 경우 (다음 위치 벽을 부수기)
                    if (maze[nx][ny] == 1 && current.breakCount == 0) {
                        visited[nx][ny][1] = visited[current.x][current.y][0] + 1;
                        deque.add(new Node(nx, ny, 1));
                    }
                }
            }
        }
        return -1;
    }

    private static class Node {
        int x;  // 현재 위치 x
        int y;  // 현재 위치 y
        int breakCount;  // 현재 위치까지 부수고 온 벽의 수

        public Node(int x, int y, int breakCount) {
            this.x = x;
            this.y = y;
            this.breakCount = breakCount;
        }
    }
}