[백준] 13656 침투 - BFS (Python3)

문제

입력과 출력

제한 조건과 설계

제한 조건

1. 미로 문제처럼 M*N 격자 그래프 문제이므로 BFS를 사용한다.
2. 1은 검은색 격자이기에 전류가 잘 통하지 않고, 0은 흰색 격자로 전류가 잘 통한다.
3. 0행에서 M-1행에 도달하는 경로가 있는 지를 물어보는 문제다.

---

자연어 알고리즘

1. 정보를 입력 받고 그래프를 생성한다.
2. 0행에서 값이 0인 좌표가 시작 지점이다. 이 지점들을 starts 리스트에 저장한다.
3. starts 중 한 지점으로 BFS 탐색을 시도 했을 때 m-1 행에 도달하면 YES를 출력하고 프로그램을 종료한다.
4. starts의 모든 지점을 시작 지점으로 BFS를 반복한다.
5. 3번에서 YES를 출력하고 종료되지 않았다면 NO를 출력하고 프로그램을 종료한다.

---

코드

import sys
from collections import deque

input = sys.stdin.readline

#행, 열
m,n = map(int,input().split())
graph = [list(map(int, input().rstrip())) for i in range(m)]
starts = [(0,i) for i in range(n) if graph[0][i] == 0]

def bfs(graph,v,m_max,n_max):
    m,n = v
    q = deque([(m,n)])
    graph[m][n] = 1

    dm,dn = [-1,1,0,0],[0,0,-1,1]

    while q:
        m,n = q.popleft()
        for i in range(4):
            nm, nn = m+dm[i], n+dn[i]

            if nm == m_max:
                print("YES")
                exit()

            if nm < 0 or nn < 0 or nn >= n_max or graph[nm][nn] == 1:
                continue

            q.append((nm,nn))
            graph[nm][nn] = 1

m_max = len(graph)
n_max = len(graph[0])

[bfs(graph,v,m_max,n_max) for v in starts]

print("NO")

---

세 줄 요약

graph = [list(map(int, input().rstrip())) for i in range(m)]

1. 격자 그래프를 생성할 때 실수했다. 한 행을 String으로 받고 map 함수로 각 String요소를 int로 형 변환해서 list에 하나씩 추가 한다음 그 list를 graph에 추가하는 과정을 반복하면 된다. 위는 격자 그래프 생성 코드이다.
2. [bfs(graph,v,m_max,n_max) for v in starts] 처럼 List Comprension을 사용하면 2줄 쓸 코드를 1줄로 줄일 수 있다.
3. dm,dn = [-1,1,0,0],[0,0,-1,1] 처럼 2줄 쓸 코드를 1줄로 줄일 수 있다.