μ•Œκ³ λ¦¬μ¦˜/λ°±μ€€ 풀이

BOJ 2178: 미둜 탐색 (Python)

adorableco 2023. 3. 14. 03:51
λ°˜μ‘ν˜•

문제

https://www.acmicpc.net/problem/2178

 

2178번: 미둜 탐색

첫째 쀄에 두 μ •μˆ˜ N, M(2 ≤ N, M ≤ 100)이 μ£Όμ–΄μ§„λ‹€. λ‹€μŒ N개의 μ€„μ—λŠ” M개의 μ •μˆ˜λ‘œ λ―Έλ‘œκ°€ μ£Όμ–΄μ§„λ‹€. 각각의 μˆ˜λ“€μ€ λΆ™μ–΄μ„œ μž…λ ₯으둜 μ£Όμ–΄μ§„λ‹€.

www.acmicpc.net

 

 

μ½”λ“œ

import sys
from collections import deque

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 nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if graph[nx][ny] == 0:
                continue
            if  graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))
    return graph[n-1][m-1]

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

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

print(bfs(0,0))

 

풀이

bfsλ₯Ό μ΄μš©ν•΄ 문제λ₯Ό ν’€μ—ˆλ‹€. (0,0) μœ„μΉ˜λΆ€ν„° 탐색을 μ‹œμž‘ν•˜μ—¬ μƒν•˜μ’Œμš°μ— μžˆλŠ” 값이 1이라면, 즉 아직 μ§€λ‚˜κ°€μ§€ μ•Šμ•˜κ³  μ§€λ‚˜κ°ˆ 수 μžˆλŠ” 길이라면 κ·Έ 값에 μ΄λ•ŒκΉŒμ§€ 온 경둜의 + 1 을 ν•œ 값을 λ„£λŠ”λ‹€. 그리고 κ·Έκ²ƒμ˜ μ’Œν‘œ 값을 큐에 λ‹΄λŠ”λ‹€.

큐에 λ‚¨λŠ”κ²Œ 없을 λ•ŒκΉŒμ§€ λ°˜λ³΅ν•˜κ³  λ‚˜λ©΄ graph[n-1][m-1] ( (0,0)λΆ€ν„° μ‹œμž‘ν–ˆμœΌλ―€λ‘œ 였λ₯Έμͺ½ κ°€μž₯ μ•„λž˜μ˜ μ’Œν‘œλŠ” (n-1, m-1)이닀. )에 λ“€μ–΄κ°€ μžˆλŠ” 값이 μ΅œμ†Œ 경둜 κ°’μœΌλ‘œ 정닡이닀. 

 

λ°˜μ‘ν˜•