👩‍🎓공부 - 2023.12.27 오늘의 백준 문제풀이

13565번 - 침투

위에서부터 잉크를 침투시키는데 아래쪽까지 닿을지 안닿을지 맞추는 문제입니다.

M,N = map(int,input().split())
graph = []
que = deque()
for _ in range(M):
    graph.append(list(map(int,input())))

격자의 가로와 세로 길이, 그리고 그래프를 받아주고 que를 하나 선언해줍시다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]
def bfs(x,y):
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=M or ny>=N:
                continue

BFS 항상 쓰는 것처럼 que선언하고 4방향 탐색을 실시해서

            if graph[nx][ny] == 0 or graph[x][y] == 0:
                graph[x][y] = 9
                graph[nx][ny] = 9
                que.append([nx,ny])

만약에 잉크를 떨어트릴수 있는 공간인 0이 나온다면 9로 숫자를 바꿔 잉크를 떨어트렸음을 표기해주겠습니다.

for i in range(len(graph[0])):
    if graph[0][i] == 0:
        bfs(0,i)

문제에서 잉크는 위에서부터 떨어트린다 했으므로 그래프 맨 위만 싹다 조사해서 BFS를 돌려주면 됩니다.

boolean = False
for j in range(len(graph[-1])):
    if graph[-1][j] == 9:
        boolean = True
        break
if boolean == True:
    print('YES')
else:
    print('NO')

그리고 만약 그래프의 하단에 9가 존재한다면 잉크가 끝까지 도달할 수 있다는 의미이므로 YES를, 아니라면 NO를 출력하면 문제를 해결할 수 있습니다.