[Python] 13565번 침투

✏️ 문제

 

문제 파악

상하좌우로 인접한 흰색 격자들로 전달될 수 있으므로 다음과 같이 방향 배열을 구성했다.

d = [(1, 0), (0, 1), (-1, 0), (0, -1)]

 

문제에서 전류가 섬유 물질의 가장 바깥쪽 흰색 격자들에만 공급된다고 했으므로 첫 째줄을 돌면서 첫 째줄의 흰색 격자들과 인접해 있는 격자들만 전류가 흐른 것으로 바뀌도록 코드를 짜면 된다.

또한 나는 안쪽까지 침투된 건지 아닌 지에 대한 기준을 잘 이해 못했었는데 찾아보니 다들 맨 아래줄의 흰색 격자가 전류가 흘렀는 지 아닌 지를 구분하여 출력하는 것을 볼 수 있었다.

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

from collections import deque

m, n = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(m)]
d = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def bfs(x, y):
  q = deque([(x, y)])
  graph[x][y] = 2
  
  while q:
    x, y = q.popleft() 

    for i in range(4):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < m and 0 <= dy < n and graph[dx][dy] == 0:
        graph[dx][dy] = 2
        q.append([dx, dy])
        
for j in range(n):
  if graph[0][j] == 0:
    bfs(0, j)

print("YES" if 2 in graph[-1] else "NO")

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS