[백준 2206번-벽 부수고 이동하기]-파이썬

solved.ac 난이도 :  GOLD4

백준    2206번- 파이썬 풀이

 

<문제>

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

2206번: 벽 부수고 이동하기

<풀이>-그래프 탐색,그래프 이론,너비 우선 탐색

이 문제는 일반적인 너비 우선 탐색문제와는 다르게 3차원 배열을 사용해야한다. 그 대표적인 이유는 벽을 부수고 이동할수 있는 경우가 딱 한번밖에 존재하지 않기 때문이다. 때문에 벽을 부수고 이동하는 경우, 벽을 부수지 않고 이동하는 경우를 각각 구하기 위해 3차원 배열을 사용해야한다. 필자는 이 문제를 처음 풀때 2차원배열을 이용한 풀이로 접근하다가 실패했다. 그러면 3차원 배열을 어떻게 사용하는지 차근차근 살펴보자

 

-3차원 배열-

 

그래프의 (0,0)위치에서 시작해 각 방향으로 이동하는 경우에서 벽을 부수고 이동하는 경우, 벽을 부수지 않고 이동하는 경우 두가지가 존재할 수 있다. 이때 다음과 같이 3차원 배열을 선언한다.

visitied = [[[0]*2 for _ in range(m)] for _ in range(n)]

이 배열이 의미하는 바는 visitied 의 x,y의 위치에 [0,0]이라는 원소를 만들어 visitied[x][y][0]은 벽을 부수고 이동하는 경로, vistieid[x][y][1]은 벽을 부수지 않고 이동하는 경로를 의미한다. 우선 이점을 정확히 이해하고 넘어가자.

 

-visitied배열에 두경우의 이동경로를 각각 저장하는 방법-

 

우선 벽을 부수지 않고 이동하는 경우를 살펴보자. 필자는 break_one_wall이라는 변수를 만들어 break_one_wall = 1인경우 벽을 부수지 않고 이동하는 경우, break_one_wall=0 인경우 벽을 부수고 이동하는 경로로 설정했다. 

 

우선 break_one_wall의 초깃값을 1로 설정해 벽을 부수지 않고 이동하는 경로로 이동을 시작한다. 

 

이렇게 이동을 할때마다 visitied[x][y][1]의 위치에 이동거리를 저장해준다.

 

그러다 벽을 만난 경우, break_one_wall의 값을 0으로 바꾼후 vistied[x][y][0]의 위치에 이동거리를 저장한다.

 

이때 벽은 한번만 부술 수 있으므로 벽을 부수고 이동할 수있는 조건에 break_one_wall=1이란 조건을 반드시 넣어주어야한다.

 

만약 인접한 방향의 값은 1이지만 break_one_wall=0이라면 이미 벽을 부순것이므로 그 방향으로의 이동은 불가능하다.

 

코드는 다음과 같다.

 queue.append((x,y,break_one_wall))
    visitied[x][y][break_one_wall] = 1
    while queue:
        x,y,break_one_wall = queue.popleft()
        if x == n-1 and y == m-1:
            return visitied[x][y][break_one_wall]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            #벽을 부수지 않고 이동
            if graph[nx][ny] == 0 and visitied[nx][ny][break_one_wall]==0:
                queue.append((nx,ny,break_one_wall))
                visitied[nx][ny][break_one_wall] = visitied[x][y][break_one_wall]+1
            if graph[nx][ny] == 1 and break_one_wall == 1:
                queue.append((nx,ny,break_one_wall-1))
                visitied[nx][ny][break_one_wall-1] = visitied[x][y][break_one_wall]+1

728x90

반응형

<코드>-파이썬

 

from collections import deque

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

graph = [list(map(int,input())) for _ in range(n)]

visitied = [[[0]*2 for _ in range(m)] for _ in range(n)]

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

def solution(x,y,break_one_wall,visitied,graph):
    queue = deque()
    queue.append((x,y,break_one_wall))
    visitied[x][y][break_one_wall] = 1
    while queue:
        x,y,break_one_wall = queue.popleft()
        if x == n-1 and y == m-1:
            return visitied[x][y][break_one_wall]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            #벽을 부수지 않고 이동
            if graph[nx][ny] == 0 and visitied[nx][ny][break_one_wall]==0:
                queue.append((nx,ny,break_one_wall))
                visitied[nx][ny][break_one_wall] = visitied[x][y][break_one_wall]+1
            if graph[nx][ny] == 1 and break_one_wall == 1:
                queue.append((nx,ny,break_one_wall-1))
                visitied[nx][ny][break_one_wall-1] = visitied[x][y][break_one_wall]+1
    return -1
print(solution(0,0,1,visitied,graph))

-마치며-

여태까지 푼 BFS문제중 가장 어려웠던 문제였던거 같다. 그동안은 2차원배열만 이용해 푸는 문제가 대부분이라 이 문제도 당연히 그럴줄 알았는데 큰 오산이었다. 앞으로 다양한 문제를 접해 사고방식을 넓힐 필요가 있을거 같다.