[TIL_Carrotww] 122 - 23/06/29

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 알고스팟

많이 풀어본 유형의 문제인데 생각이 안나서 조금 애먹었다.
두 가지 방법으로 풀었다.
깔끔한건 BFS 풀이인것 같지만 개인적으로는 다익스트라 풀이가 마음에 든다.

• BFS 풀이

def solve():
    import sys
    from collections import deque
    input = sys.stdin.readline

    col, row = map(int, input().split())
    graph = [list(map(int, input().strip())) for _ in range(row)]

    queue = deque()
    queue.append((0, 0))
    dr, dc = [0, 0, 1, -1], [1, -1, 0, 0]
    visited = [[-1] * col for _ in range(row)]
    visited[0][0] = 0

    while queue:
        cur_row, cur_col = queue.popleft()

        for i in range(4):
            n_row, n_col = cur_row+dr[i], cur_col+dc[i]
            if (n_row < 0 or n_row >= row) or (n_col < 0 or n_col >= col):
                continue
            if visited[n_row][n_col] == -1:
                if graph[n_row][n_col] == 0:
                    visited[n_row][n_col] = visited[cur_row][cur_col]
                    queue.appendleft((n_row, n_col))
                else:
                    visited[n_row][n_col] = visited[cur_row][cur_col] + 1
                    queue.append((n_row, n_col))
    print(visited[row-1][col-1])

if __name__ == "__main__":
    solve()

BFS로 벽이 막혀있으면 deque에 뒤에 추가해주고 막혀있지 않다면 큐의 맨 앞에 추가해주어서 벽이 없을때 갈 수 있을만큼 최대한 보내버린다.

• 다익스트라 풀이

def solve1():
    import sys, heapq
    input = sys.stdin.readline

    col, row = map(int, input().split())
    graph = [list(map(int, input().strip())) for _ in range(row)]

    # wall break, row, col
    heap = [(0, 0, 0)]
    dr, dc = [1, -1, 0, 0], [0, 0, 1, -1]
    visited = [[-1] * col for _ in range(row)]
    visited[0][0] = 1

    while heap:
        cur_break, cur_row, cur_col = heapq.heappop(heap)
        for i in range(4):
            n_row, n_col = cur_row+dr[i], cur_col+dc[i]
            if n_row == row-1 and n_col == col-1:
                print(cur_break)
                return
            if (n_row < 0 or n_row >= row) or (n_col < 0 or n_col >= col) or visited[n_row][n_col] == 1:
                continue
            visited[n_row][n_col] = 1
            if graph[n_row][n_col] == 1:
                heapq.heappush(heap, (cur_break+1, n_row, n_col))
            else:
                heapq.heappush(heap, (cur_break, n_row, n_col))
    print(0)

if __name__ == "__main__":
    solve1()

반례 하나를 못 찾아서 애먹었다 ㅠㅠㅠㅠㅠ
99퍼센트에서 계속 틀리길래 뭘까 하면서 생각을 해봤는데
row, col이 둘 다 1로 주어지면 정답을 구하지 못하는 코드여서 while문을 통과하면 (출발지에서 출발해 다음 지점에 정답이 없다는 말) print 0을 해주었다.