[백준]2178 - 미로탐색 with.Python

문제 분석 요약

-- 문제 --

입력 : N, M(2 ≤ N, M ≤ 100)

• (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수 구하기.(서로 인접한 칸으로만 이동, 칸을 셀 때에는 시작 위치와 도착 위치도 포함)

💡알고리즘 설계

💡코드

💡시간복잡도

O(N)

💡틀린 이유

💡틀린 부분 수정 or 다른 풀이

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split())
array=[]

for i in range(n):
    array.append(list(map(int,sys.stdin.readline().strip())))

d = [[1,0],[0,1],[-1,0],[0,-1]]

def bfs(y,x):
    queue = deque()
    queue.append((y,x))
    while queue:
        y1,x1 = queue.popleft()
        for dx,dy in d:
            if 0<=y1+dy<n and 0<=x1+dx<m:
                if array[y1+dy][x1+dx]==1:
                    array[y1+dy][x1+dx]=array[y1][x1]+1
                    queue.append((y1+dy,x1+dx))


bfs(0,0)
print(array[n-1][m-1])

💡느낀점 or 기억 할 정보

1. 처음 코테를 접하다보니 접근하는데 어려움을 느낌. -> 문제 많이 접해보기.

2. 개념만 공부하지 말고 기본 구현한 코드 많이 접해보기.

3. dx, dy : 미로 문제를 풀 때 이동을 표현해준다.

4. array[y1+dy][[x1+dx]= array[y1][x1]+1 : 만약 (0,0)에서 (0,1)로 이동한다면 1+1=2가 됨. 즉 (0,1)에 도달하는데 최소 2번의 이동이 필요함을 의미.

5. print(array[n-1][m-1]) : 미로의 맨 마지막 칸의 값 의미(오른쪽 아래)
   0 부터 시작하니까 -1해주기.

-출처 : https://coooco.tistory.com/76 풀이법 익히는 것을 목표로 하였습니다.