백준 2178 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

문제를 처음 봤을 때는 금방 풀 수 있겠다 생각했다.

 

얼마 지나지 않아 내 생각은 완전히 부서졌다.

 

풀이를 찾아보고, 얼추 접근 방법에서는 맞았지만 도저히 구현을 할 수 없겠다 생각했다.

 

그래서 처음으로 타인의 코드를 보고 이해한 상태로 포스팅한다.

 

처음엔 dp문제일 거라 생각했는데, bfs 문제였다.

 

코드

import sys as s

from collections import deque

n,m = map(int,s.stdin.readline().split())

array = []

location = [0,0]

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

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

for i in range(int(n)):

    array.append(list(map(int,input())))

def bfs(x,y):

    queue = deque()

    queue.append((x,y))

    while queue:

        x, y = queue.popleft()

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and array[nx][ny] == 1:

                queue.append((nx, ny))

                array[nx][ny] = array[x][y] + 1

    return array[n-1][m-1]

print(bfs(0,0))

큐를 사용했다.

 

아직까지 어떤 상황에서 큐를 사용해야 할지 감이 잡히지 않는다.

 

지금 내가 알고 있는 바로, bfs는 큐를 사용한다. 정도이다.

 

코드에 대한 이해는 했다.

 

조금 더 시간을 투자하면 유의미한 결과가 나오겠지 하며, 많은 아쉬움을 남긴 채로 이번 포스팅을 마무리한다.

 

추후에 비슷한 유형의 문제를 다시 만났을 땐, 반드시 풀어내리라.

 

출처 : https://yuna0125.tistory.com/61

[백준🥈1] #2178 미로 탐색 (python)