[백준(Python/Java)] 2206_벽 부수고 이동하기(BFS)

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

일반적인 BFS 문제에서 "벽을 부술 수 있는 기회가 1회" 추가된 문제입니다. 따라서 이 문제를 해결하기 위해서는 "어느 벽 하나를 부술 것인가?"를 정할 수 있어야 합니다.

 

하지만, 임의의 벽을 하나 제거하고 BFS를 수행하는 행위를 반복하면 시간초과가 발생하기 때문에 한 번의 BFS를 진행하는동안 "벽을 부순 상태인지, 부수지 않은 상태인지'를 큐에 담고 다녀야 합니다.

 

다시 말해서, 임의의 지점 (x, y)에서의 내가 이미 벽을 부순 적이 있다면 그 곳에서 움직일 수 있는 곳은 벽이 아닌 공간이 될 것이고 벽을 부순 적이 없다면 벽인 곳도 하나 깨고 움직일 수 있다는 것이죠.

 

이를 기록하기 위해서 visited 배열은 3차원 배열로 만들어줍니다. visited[x][y][breakWall]에서 x, y는 현재 위치를 의미하고, breakWall은 0이면 부순 적이 없을 때, 1이면 부순 적이 있을 때를 의미합니다.

 

이렇게 visited 배열을 만들어주면, 그 이후 풀이는 일반적인 BFS와 동일합니다.

 

아래는 파이썬 코드와 자바 코드입니다.

 

[풀이 - Python]

import sys
from collections import deque

def bfs():
    # 이동할 수 있는 방향
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]

    #visited[x][y][breakWall] = (x,y) 지점의 breakWall한 상태에서 거리
    visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    visited[0][0][0] = 1


    # 큐에 처음 거리 1과 시작점 (0,0), 벽을 부순 횟수(0)을 넣고 시작
    q = deque()
    q.append((0,0,0))
    result = []
    while q:
        x, y, breakWall = q.popleft()
  
        if x == n-1 and y == m-1:
            result.append(visited[x][y][breakWall])

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 이동할 위치가 벽인 경우 현재 벽을 한 번도 부수지 않았으면 벽을 부수고 이동    
                if graph[nx][ny] == 1:
                    if visited[nx][ny][1] == 0 and breakWall == 0:
                        visited[nx][ny][1] = visited[x][y][0] + 1
                        q.append((nx, ny, 1))
                # 벽이 아닌 경우
                else:
                    if visited[nx][ny][breakWall] == 0:
                        visited[nx][ny][breakWall] = visited[x][y][breakWall] + 1
                        q.append((nx, ny, breakWall))

    return min(result) if result else -1  


n, m = map(int, input().split())

# graph 정보
graph = [[] for _ in range(n)]
for i in range(n):
    graph[i] = list(map(int, sys.stdin.readline().rstrip()))

print(bfs())

 

 

[풀이 - JAVA]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class B_2206 {

    static class Point{
        int x, y, breakWall;

        Point(int x, int y, int breakWall){
            this.x = x;
            this.y = y;
            this.breakWall = breakWall;
        }
    }
    public static int n, m, result = 0;
    public static char[][] graph;
    public static int[][][] visited;

    // 이동할 수 있는 방향
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};

    public static int bfs(){
        ArrayDeque<Point> q = new ArrayDeque<>();
        visited = new int[n][m][2];
        visited[0][0][0] = 1;

        // 큐에 처음 거리 1과 시작점 (0,0), 벽을 부순 횟수(0)을 넣고 시작
        q.offer(new Point(0,0,0));

        while(!q.isEmpty()){
            Point curr = q.poll();
            int x = curr.x;
            int y = curr.y;
            int breakWall = curr.breakWall;

            if(x == n-1 && y == m-1){
                return visited[x][y][breakWall];
            }

            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(0 <= nx && nx < n && 0 <= ny && ny < m){
                    // 이동할 위치가 벽인 경우 현재 벽을 한 번도 부수지 않았으면 벽을 부수고 이동
                    if(graph[nx][ny] == '1'){
                        if(visited[nx][ny][1] == 0 && breakWall == 0){
                            visited[nx][ny][1] = visited[x][y][0] + 1;
                            q.offer(new Point(nx,ny, 1));
                        }
                    }
                    // 벽이 아닌 경우
                    else{
                        if(visited[nx][ny][breakWall] == 0){
                            visited[nx][ny][breakWall] = visited[x][y][breakWall] + 1;
                            q.offer(new Point(nx, ny, breakWall));
                        }
                    }
                }
            }

        }
        return -1;

    }


    public static void main(String[] args) throws Exception{
        // Input 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new char[n][m];
        for(int i = 0; i < n; i++){
            graph[i] = br.readLine().toCharArray();
        }

        result = bfs();
        System.out.println(result);
        br.close();
    }

}