2178

날짜 : 2022. 10. 25

사용 언어 : python

 

문제

 

코드

import sys
from collections import deque

def bfs():
    # 상하좌우 탐색
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    q.append([0, 0]) # 시작점, 이동거리
    while q:
        node = q.popleft()
        #print(node)
        for i in range(4):
            # 이중 for문 사용 -> 순환과정 주의
            x = node[0] + dx[i]
            y = node[1] + dy[i]
            if x not in range(n) or y not in range(m): # 범위이탈
                continue
            if graph[x][y] == 0: # 벽에 부딫힌 경우
                continue
            if graph[x][y] == 1:
                q.append([x, y])
                graph[x][y] = graph[node[0]][node[1]] + 1 # 방문처리
    #print(graph)
    print(graph[n-1][m-1])

n, m = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n)]
q = deque()

for i in range(n):
    tmp = (sys.stdin.readline().strip())
    for j in range(len(tmp)):
        graph[i].append(int(tmp[j]))

#print(graph)
bfs()

 

 

알게된 점

- BFS를 활용해서 풀이하는 문제였다.

- 탐색과정에서 그래프의 방문처리와 dx, dy에서의 반복조건을 제대로 하지 않아 많은 시간을 할애하게 만들었다.

- 단순 방문했을 때 1을 0으로 만들어 다시 갈 수 없게 했지만 네 번째 예시에서 계속 값이 14가 나왔다. 방문횟수를 최소로 해야 했기 때문에 이를 해결하려고 고민했고 그래프가 1인 경우에만 방문해서 값을 변경한다는 조건을 추가했다.

- 기본적인 원리는 맞았지만 유려하게 할 수 없어서 아직 많이 아쉽다.

- 많이 문제를 풀어봐야겠다.

 

 

참고 사이트

-