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

BFS 문제 

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

2206번: 벽 부수고 이동하기

 

(1) 처음에 생각한 방식 - V1 (실패)

# 벽 부수고 이동하기 (골드 3) / BFS
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n)]
visited = [[False] * m for _ in range(n)]
for i in range(n):
    l = list(sys.stdin.readline().strip())
    for j in l:
        graph[i].append(int(j))

def bfs(startY, startX, n, m):
    queue = deque()
    previousCnt = 1
    queue.append((previousCnt, startY, startX))
    visited[startY][startX] = True
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    chance = True 
    findZero = False

    while queue:
        cnt, y, x = queue.popleft()
        if y == n-1 and x == m-1: return cnt

        if previousCnt < cnt: 
            if findZero == False:
                chance = False
            previousCnt = cnt
        # currentCnt = max(currentCnt, cnt)
        for i in range(4):
            nextY = dy[i] + y
            nextX = dx[i] + x
            # print("nextYX: ", nextY, nextX, "chance: ", chance, "cnt: ", cnt, "previousCnt", previousCnt)
            # print(queue)

            if 0 <= nextX < m and 0 <= nextY < n:
                if visited[nextY][nextX] == True: continue
                if chance == True:
                    if graph[nextY][nextX] == 0: findZero = True
                    queue.append((cnt + 1, nextY, nextX))
                else:
                    if graph[nextY][nextX] == 0:
                        queue.append((cnt + 1, nextY, nextX))
                visited[nextY][nextX] = True
    
    return -1

print(bfs(0, 0, n, m))

 

처음엔 딱 문제의 예제 입력만 보고, 코드를 위와 같이 짰다. 이랬더니 문제 예제는 맞았지만, 결과적으로 18%에서 틀렸다.

 

▪︎ 위의 코드

• 벽을 부술 수 있는지, 없는지를 chance라는 boolean 변수로 나타냈다.
• 위의 핵심 로직은 BFS에서 queue를 이용하여 값을 넣고 뺀다는 특징을 이용했다. 다음 그림에서, 같은 형광펜으로 칠한 좌표끼리 같은 loop에 queue에 넣고 빼짐을 의미한다. 따라서, 한 loop 안에서 0이 있으면 벽을 부수지 않고 그냥 해당 경로로 이동하고, 한 loop에서 0(지나갈 수 있는 노드)이 없을 때에만 벽을 부수고 이동하면 된다고 생각했다. 

 

하지만, 이는 너무 예제에 특화된 코드였다.

 

(2) 처음에 생각한 방식 - V2 (실패)

# 벽 부수고 이동하기 (골드 3) / BFS
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n)]
visited = [[False] * m for _ in range(n)]
wall = [[0] * m for _ in range(n)]
for i in range(n):
    l = list(sys.stdin.readline().strip())
    for j in l:
        graph[i].append(int(j))


def bfs(startY, startX, n, m):
    queue = deque()
    previousCnt = 1
    queue.append((previousCnt, startY, startX))
    visited[startY][startX] = True
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]

    while queue:
        cnt, y, x = queue.popleft()
        if y == n-1 and x == m-1: return cnt

        for i in range(4):
            nextY = dy[i] + y
            nextX = dx[i] + x

            if 0 <= nextX < m and 0 <= nextY < n:
                if visited[nextY][nextX] == True: continue
                # if graph[nextY][nextX] == 1 and wall[y][x] == 1: continue

                print("nextYX: ", nextY, nextX, "yx:", y, x, "cnt: ", cnt, "wall YX", wall[y][x])

                if graph[nextY][nextX] == 0:
                    queue.append((cnt + 1, nextY, nextX))
                    wall[nextY][nextX] = wall[y][x]
                    visited[nextY][nextX] = True
                else:
                    if wall[y][x] == 0:
                        queue.append((cnt + 1, nextY, nextX)) 
                        wall[nextY][nextX] = 1
                        visited[nextY][nextX] = True
    print(cnt)
                
    return -1
    
print(bfs(0, 0, n, m))

예제 1과 예제 2의 경우는 모두 맞았지만, V1과 마찬가지로 다음 예제와 같은 경우에서 오답이 나왔다.

 

6 5

00000

11110

00000

01111

01111

00010

 

출력 : 8

정답 : 18

 

▪︎ 위의 코드

 

1) 벽을 부쉈는지/안부쉈는지의 여부를 저장하는 wall이란 2차원 배열을 만들고(n x m), 0으로 초기화를 해주었다.

2) graph[nextY][nextX] == 0인 경우는 그냥 지나갈 수 있으므로 wall[nextY][nextX] 값을 wall[y][x] 값으로 대입해주었다. (벽을 안부쉈으므로) 또, 방문 처리를 해주었다.

3) graph[nextY][nextX] == 1인 경우는 그냥 지나갈 수 없으므로 벽을 부숴야 한다. 따라서 아직 벽을 부순 적이 없는 경우에만 queue에 넣고, wall[nextY][nextX] 값을 바꿔주며 방문처리를 해주었다.

 

▪︎ 문제점

위의 코드에선 문제점이 있다. BFS의 특성상 queue를 사용하기 때문에, 위의 사진처럼 먼저 방문한 노드를 방문처리해주면(핑크색 루트) 다음 번에 최단거리의 가능성이 있는 루트(초록색 루트)에서 방문을 못하게 될 수도 있다.

핑크색 루트처럼 벽을 한번 부쉈는데, 또 벽을 만나 더이상 갈 수 없는 경우에는 왔던 루트를 다시 되돌아가며 첫번째 벽을 만날때까지 visit 여부를 False로 바꿔줘야 되나도 생각했는데, 이는 절대 좋은 방법이 아니라고 생각됐다.

따라서, 방문 처리 조건이나 해당 로직을 실행하는 조건을 바꿔보려고 했지만, 쉽게 생각이 나지 않고 무한 loop에 빠지는 경우가 대부분이라서 코드를 그냥 새로 짜기로 했다.

# 이렇게 조건 추가했으나 무한 루프에 빠짐
if visited[nextY][nextX] == True and wall[y][x] == 0: continue

 

💡 풀이 코드 

# 벽 부수고 이동하기 (골드 3) / BFS
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n)]
# visited = [[0] * m for _ in range(n)]
visited = [[[0] * 2 for _ in range(m)]for _ in range(n)]
for i in range(n):
    l = list(sys.stdin.readline().strip())
    for j in l:
        graph[i].append(int(j))
# print(visited)

# for i in range(n):
#     print(visited[i])
    
def bfs(startY, startX, n, m, wallLeft):
    queue = deque()
    queue.append((startY, startX, wallLeft))
    visited[startY][startX][wallLeft] = 1
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]

    while queue:
        y, x, wallLeft = queue.popleft()
        if y == n - 1 and x == m - 1 : return visited[y][x][wallLeft]

        for i in range(4):
            nextY = dy[i] + y
            nextX = dx[i] + x

            if 0 <= nextX < m and 0 <= nextY < n:
                if graph[nextY][nextX] == 0:
                    if visited[nextY][nextX][wallLeft] == 0:
                        visited[nextY][nextX][wallLeft] = visited[y][x][wallLeft] + 1
                        queue.append((nextY, nextX, wallLeft))
                else:
                    if wallLeft == 1:
                        visited[nextY][nextX][wallLeft - 1] = visited[y][x][wallLeft] + 1
                        queue.append((nextY, nextX, wallLeft - 1))
    return -1

print(bfs(0, 0, n, m, 1))

 

▪︎ 위의 코드

1) 벽을 부쉈는지/안부쉈는지의 여부를 나타낼 수 있도록 visit 배열을 2차원 배열이 아닌 3차원 배열로 만들어주었다.

-> 벽을 부쉈는지/안부쉈는지를 나눠 벽을 부순 경우에는 visit[][][0]으로 이동하고, 벽을 부수지 않은 경우에는 visit[][][1]로 이동하게 하였다. 즉, 이동 중에 벽을 부쉈는지 여부에 따라 서로 다른 경로로 이동하여 다시 방문할 수 있는 기회를 만들어주었다. (즉, V2 버전 문제점 해결)

 

2) 기존에는 wall 2차원 배열을 이용하여 해당 위치에서 벽을 부쉈는지 여부를 판단했지만, 이제 queue에 벽을 부쉈는지를 알 수 있는 변수 wallLeft를 넣고 빼며 이를 판단한다.

 

3) 기존에는 해당 위치까지 얼마나 이동했는지를 나타내는 변수 cnt를 queue에 넣고 뺐지만, 현재는 해당 위치까지 이동한 거리를 visit 배열에 기록한다.

 

▪︎ 핵심 로직

• graph[nextY][nextX] == 1 and wallLeft == 1: 벽을 부수고 visit[nextY][nextX][0]으로 이동
• graph[nextY][nextX] == 1 and wallLeft == 0: 벽을 더이상 부술 수 X -> 이동 불가, queue에 더이상 삽입 X
• graph[nextY][nextX] == 0 and wallLeft == 1: 그냥 visit[nextY][nextX][1]로 지나가면 됨.
• graph[nextY][nextX] == 0 and wallLeft == 0: 그냥 visit[nextY][nextX][0]로 지나가면 됨.

if graph[nextY][nextX] == 0:
	if visited[nextY][nextX][wallLeft] == 0:
    	visited[nextY][nextX][wallLeft] = visited[y][x][wallLeft] + 1
        queue.append((nextY, nextX, wallLeft))
else:
	if wallLeft == 1:
    	visited[nextY][nextX][wallLeft - 1] = visited[y][x][wallLeft] + 1
        queue.append((nextY, nextX, wallLeft - 1))

 

graph[nextY][nextX] == 1 인 경우 : wallLeft가 남은 경우에만 벽을 부수고 visit[nextY][nextX][0]으로 이동한다.

graph[nextY][nextX] == 0 인 경우 : 그냥 visit[nextY][nextX][wallLeft]로 지나가면 된다. 단, visit[nextY][nextX][wallLeft]가 0일 경우(처음 방문하는 경우)에만 실행되도록 하여 무한루프를 막아주었다. 벽을 부쉈는지/안부쉈는지를 visit[][][0]과 visit[][][1]로 나누었기 때문에, visit[nextY][nextX][wallLeft]가 0이 아닌 경우에는 이미 방문했단 뜻이므로 해당 경로는 최단경로가 아니다. 따라서 로직을 실행할 필요가 없다.

 

따라서, while문 부분을 다음과 같이 작성해도 된다. 이렇게 작성하는게 좀 더 직관적일 것 같다.

    while queue:
        y, x, wallLeft = queue.popleft()
        if y == n - 1 and x == m - 1 : return visited[y][x][wallLeft]

        for i in range(4):
            nextY = dy[i] + y
            nextX = dx[i] + x

            if 0 <= nextX < m and 0 <= nextY < n:
                if visited[nextY][nextX][wallLeft] != 0: continue
                
                if graph[nextY][nextX] == 0:
                    visited[nextY][nextX][wallLeft] = visited[y][x][wallLeft] + 1
                    queue.append((nextY, nextX, wallLeft))
                else:
                    if wallLeft == 1:
                        visited[nextY][nextX][wallLeft - 1] = visited[y][x][wallLeft] + 1
                        queue.append((nextY, nextX, wallLeft - 1))

 

 

 

느낀점 : 너무 쌩자 구현으로 문제를 해결하려 했던 것 같은데, 좀 더 단순화되고, 직관적인 접근이 필요할 것 같다.

 

*참고

https://herong.tistory.com/entry/BOJ-2206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-Java

[BOJ] 2206. 벽 부수고 이동하기 (Java)

https://hongcoding.tistory.com/18

[백준] 2206 벽 부수고 이동하기 (Python 파이썬)

https://data-flower.tistory.com/85

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

https://www.acmicpc.net/board/view/131562

글 읽기 - 18%에서 통과하시는 분들은 최대 거리를 다시 확인해 보세요!