DevKim

[Python] 백준 #2178 미로 탐색 본문

알고리즘 PS

[Python] 백준 #2178 미로 탐색

on_doing 2021. 1. 16. 18:58
728x90

www.acmicpc.net/problem/2178

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

그래프 문제의 감이 잡히는 문제

from collections import deque
import sys

que = deque()
n, m = map(int, sys.stdin.readline().rstrip().split())
List = []

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

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


que.append([0, 0])

while que:
    p = que.popleft()
    x = p[0]
    y = p[1]

    for i in range(4):
        xx = dx[i]
        yy = dy[i]

        if x + xx < 0 or x + xx >= n or y + yy < 0 or y + yy >= m:
            continue

        else:
            if List[x + xx][y + yy] == 1:
                que.append([x + xx, y + yy])
                List[x + xx][y + yy] = List[x][y] + 1

print(List[n - 1][m - 1])
728x90

'알고리즘 PS' 카테고리의 다른 글

[Python] 백준 #2667 단지번호붙이기  (0) 2021.01.16
[Python] 백준 #2331 반복수열  (0) 2021.01.16
[Python] 백준 #11724 연결 요소의 개수  (0) 2021.01.16
[Python] 백준 #10451 순열 사이클  (0) 2021.01.16
[Python] 백준 #7576 토마토 시간단축 성공!!!!  (0) 2021.01.16
'알고리즘 PS' Related Articles more
Comments