[백준] 2206 벽 부수고 이동하기 와 나의 시행착오들 기록

최단거리 찾는 문제인데 벽하나 부술수있다는 게 특이점이다 

풀이 1 :시간초과가 났다 이중포문으로 백트래킹은 무리였던건가 ㄱ- 파이썬만 그런지 c++도 그런지 궁금하다 진짜 

이 경우, 내가 가는 경로 중에 벽이 있는지 상관없이, 모든 벽을 한번씩 다 없애보는 코드인데, 효율성을 높이려면 내가 가는 경로 도중에 마주친 벽을 제거해야 할 것 같다..

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(): # 최단 경로 구하기
    dist = [[-1] * m for _ in range(n)]
    q = deque()
    q.append((0, 0))
    dist[0][0] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1 and graph[nx][ny] == 0:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

    return dist[n-1][m-1]

result = INF
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            graph[i][j] = 0
            temp = bfs()
            if temp != -1:
                result = min(result, temp)
            graph[i][j] = 1


if result == INF:
    print(-1)
else:
    print(result)

 

풀이 2: 

벽 부순 상태를 저장하는 표를 따로 만든 경우 

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(): # 최단 경로 구하기
    check = [[False] * m for _ in range(n)] # 벽 부수기를 했는지 확인
    dist = [[-1] * m for _ in range(n)] # 최단거리

    q = deque()
    q.append((0, 0))
    dist[0][0] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1:
                if graph[nx][ny] == 0:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
                if graph[nx][ny] == 1 and check[x][y] == False:
                    check[nx][ny] = True
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))

    print(dist)
    return dist[n-1][m-1]


temp = bfs()
print(temp)

그런데 이 방법도 오류가 있다 ;; 나는 좌표 x, y 까지 오기까지 벽을 부순적이 있는지 없는지를 저장하고, 벽을 부순 적이 없다면 nx, ny로 새롭게 이동할 때 벽을 부셔도 된다라고 가정했다 

그러나 결국 벽을 부순 후의 최종 결과와 벽을 부수지 않은 후의 결과를 비교해야 하는데, 두 값을 모두 가지고 있어야 한다. 나는 벽을 부수지 않았을 때의 결과를 가지고 있지 않은 것이다 

따라서 dist에 축 하나를 더 만들어 주어야 한다. 

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

질문 게시판의 답변을 좀 참고 했다 나랑 비슷한 고민을 하시는 분이 있어서 ㅎㅎ 

글 읽기 - 왜 틀렸는지 잘 모르겠습니다. 알려주세요ㅠㅠ

 

풀이 3 : 벽을 부수는 상태도 같이 저장해준다 ! 

 

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(): # 최단 경로 구하기
    dist = [[[-1]*2 for _ in range(m)] for _ in range(n)]
    q = deque()
    q.append((0, 0, 0)) # x, y, crash
    dist[0][0][0] = 1 # 최단 거리
    while q:
        x, y, crash = q.popleft()
        if x == n-1 and y == m-1:
            return dist[x][y][crash]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0 and dist[nx][ny][crash] == -1:
                    dist[nx][ny][crash] = dist[x][y][crash] + 1
                    q.append((nx, ny, crash))
                if graph[nx][ny] == 1 and crash == 0:
                    dist[nx][ny][crash +1] = dist[x][y][crash] + 1
                    q.append((nx, ny, crash+1))
    return -1

print(bfs())

후후 어렵군