[백준] 2206. 벽 부수고 이동하기 python

🐳 링크

백준 벽 부수고 이동하기

🐕 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

🐾 풀이 방법

bfs문제에 벽을 부수는 조건이 추가된 문제이다.
방문했다는 것을 확인하기 위한 visit 배열을 단순히 [0] 이 아닌 [0,0]과 같이 나타내어 [0]번째에는 무조건 벽을 부순 경우가 들어가도록 설정한다.

특히 처음에 queue에 값을 삽입할 때, 현재 위치를 나타내는 (x,y)에 breakCount 즉 벽을 부술 수 있는 가짓수인 1을 함께 넣어 (x,y,breakCount)와 같이 받는다. 이후 벽을 부순 경우에는 breakCount = 0이 되도록 한다..!

따라서 x,y,breakCount 를 queue에서 빼낸 뒤, Map이 벽이고 breakCount가 1인 경우에는 벽을 부수고 지나가도록 하고, visit배열을 업데이트 해 준다.

오늘 푼 문제 모두 풀이를 횡설수설하는 기분...

궁금한 점🧐

하지만 매우 궁금한 점이 있다.
아래 두 소스코드를 보면 알겠지만, bfs 과정을 함수화한 것과 그렇지 않은 것 두가지인데, 함수화한 경우에는 python3에서 시간초과가 나지 않고 함수화하지 않은 경우에는 python3에서 시간초과가 난다.
그래서 함수화하지 않은 경우에

• Map을 받을 때 map함수를 통해 int로 변환시키는 코드로 변경하기
• Map == 1과 Map == 0 부분을 if-elif 구문으로 변경하기
  등등으로 변경해보았지만 여전히 시간초과가 나고, 코드는 아무 변경 없이 함수화시키면 바로 pass가 나왔다.

도저히 모르겠어서 time 패키지를 활용하여 time.perf_counter()로 시간 측정을 해 보았는데, 아래 예제에 대해서는 심지어 함수화하지 않은 코드가 더 빨랐다..

6 4
0100
1110
1000
0000
0111
0000

함수화 코드: 0.0009308000000000094
함수화하지 않은 코드: 0.0007831999999999978
도대체 무슨 이유일까?!?!?!?!?

소스코드

python3으로 했을 때 통과한 코드

import sys
n, m = map(int, sys.stdin.readline().split())
Map = list()
for _ in range(n):
    temp = sys.stdin.readline().strip()
    temp = list(map(lambda x: int(x), temp))
    Map.append(temp)


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

def bfs():
    queue = [(0, 0, 1)]
    visit = [[[0] * 2 for i in range(m)] for i in range(n)]
    visit[0][0][1] = 1

    while queue:
        x, y, breakCount = queue.pop(0)
        if x == n - 1 and y == m - 1:
            return visit[x][y][breakCount]


        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if Map[nx][ny] == 0 and visit[nx][ny][breakCount] == 0:
                    queue.append((nx, ny, breakCount))
                    visit[nx][ny][breakCount] = visit[x][y][breakCount] + 1
                if Map[nx][ny] == 1 and breakCount == 1:  # 벽이고, 벽을 부수지 않은 경우
                    queue.append((nx, ny, 0))
                    visit[nx][ny][0] = visit[x][y][1] + 1
    return -1

print(bfs())

python3으로 하면 시간초과, Pypy3으로 하면 통과

import sys

n, m = map(int, sys.stdin.readline().split())
Map = list()
for _ in range(n):
    temp = sys.stdin.readline().strip()
    temp = list(map(lambda x: int(x), temp))
    Map.append(temp)

queue = [(0, 0, 1)]
visit = [[[0] * 2 for i in range(m)] for i in range(n)]
visit[0][0][1] = 1
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
count = -1

while queue:
    x, y, breakCount = queue.pop(0)
    if x == n - 1 and y == m - 1:
        count = visit[x][y][breakCount]
        break

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if Map[nx][ny] == 0 and visit[nx][ny][breakCount] == 0:
                queue.append((nx, ny, breakCount))
                visit[nx][ny][breakCount] = visit[x][y][breakCount] + 1
            if Map[nx][ny] == 1 and breakCount == 1:  # 벽이고, 벽을 부수지 않은 경우
                queue.append((nx, ny, 0))
                visit[nx][ny][0] = visit[x][y][1] + 1

print(count)