문제
인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.
김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.
(a) The current percolates.
(b) The current does not percolate.
예를 들어, Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b)에서는 그렇지 못한다.
입력
첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.
출력
바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.
그렇지 않으면 NO를 출력한다.
예제 입력 1
5 6
010101
010000
011101
100011
001011예제 출력 1
NO예제 입력 2
8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011예제 출력 2
YES최종 코드(진행 했던 코드 포함)
#1. 전류 침투하는 섬유 물질 (MxN 격자)
#1-1. 위쪽-바깥쪽, 아래쪽-안쪽 // 검정 or 흰색
#1-2. 검정-전류 차단, 흰색-전류 통함
#1-3. 전류는 바깥 흰색 격자에 의해 공급 / 이후 상하좌우 인접 흰색 격자로 전달
#2. 첫째줄 M(줄) N(칸)개의 0또는 1
#2-1. 0-전류 통하는 흰색 / 1-전류 안통하는 검은색
#3. 안쪽까지 전달되면 YES / 아니면 NO
#===============================
# (x,y) x는 0부터 시작 그래서 '0'이 있으면 움직이고 '1'이 있으면 못감
# x가 M줄까지 가는 동안 반복 시키기(while)
# 방문한 적있는 곳도 체크해줘야함
# 0인 격자를 큐에 넣고 방문도 표시
# 현재 위치도 설정해줘야 움직여줄 수 있음
# 즉, 움직이는 현재 위치, 방문한 적있는 값 둘 다 체크해야 전진 가능
# 마지막 줄 방문 되면 print ('YES') 안되면 ("NO")
import sys
from collections import deque
# M, N 숫자화
M, N = map(int, sys.stdin.readline().split())
# 격자
grid = [sys.stdin.readline().strip() for _ in range(M)]
# 방문 여부 최초 리스트
visited = [[False]*N for _ in range(M)]
# 움직일 방향
directions = [(-1,0), (1,0), (0, -1), (0, 1)]
# BFS 탐색(앞 뒤로 빼고 넣을 수 있음)
queue = deque()
# 첫 번째 행의 흰색 격자 큐에 넣기
for j in range(N):
if grid[0][j] == '0':
queue.append((0, j))
visited[0][j] = True
# BFS 탐색
while queue:
x, y = queue.popleft()
# 현재 위치가 마지막 행인지 체크
if x == M - 1:
print("YES")
sys.exit(0)
# 상하좌우 격자 탐색
for dx, dy in directions:
nx, ny = x + dx, y+ dy
if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] == '0' and not visited[nx][ny]:
queue.append((nx, ny))
visited[nx][ny] = True
# 마지막 행 도달 X
print('NO')앞에 분석은 #만 봐도 이해될만하게 정리해서 스킵
import sys
from collections import deque
# M, N 숫자화
M, N = map(int, sys.stdin.readline().split())
# 격자
grid = [sys.stdin.readline().strip() for _ in range(M)]
# 방문 여부 최초 리스트
visited = [[False]*N for _ in range(M)]
# 움직일 방향
directions = [(-1,0), (1,0), (0, -1), (0, 1)]
# BFS 탐색(앞 뒤로 빼고 넣을 수 있음)
queue = deque()항상 입력 값을 어떤식으로 받아와야할까?가 어려운 것 같다
이 문제는 움직일 이동, 움직였던 좌표에 대한 값을 체크해줘야하기에, 쉽게 앞에넣고 빼고 이런 느낌을 위해 deque를 사용했다.
그리고 몇번 풀면 visited라는 새로운 리스트 형성해서 최초 False로 다 박아놓은 후 True로 변모시켜주는 방식도 자주 보게 된다.
물론 움직일 방향도!
# 첫 번째 행의 흰색 격자 큐에 넣기
for j in range(N):
if grid[0][j] == '0':
queue.append((0, j))
visited[0][j] = True맨 위에서 아래로 내릴 예정이기 때문에, 맨 위에서 O를 찾아 queue와 visited에 넣어주고 진행 시작
# BFS 탐색
while queue:
x, y = queue.popleft()
# 현재 위치가 마지막 행인지 체크
if x == M - 1:
print("YES")
sys.exit(0)
# 상하좌우 격자 탐색
for dx, dy in directions:
nx, ny = x + dx, y+ dy
if 0 <= nx < M and 0 <= ny < N and grid[nx][ny] == '0' and not visited[nx][ny]:
queue.append((nx, ny))
visited[nx][ny] = True
# 마지막 행 도달 X
print('NO')BFS 탐색을 통해 queue에 값이 담겨있으면 계속되는 반복문,
popleft를 통해 좌표를 움직였을 때 담아주는 x, y
그리고 상하좌우 움직여주는 dx, dy를 포함한 nx,ny
이 구조를 몇번 풀면 확실히 이해될 것 같다!
