[백준] 2606번-(Python 파이썬) - Bfs, Dfs

문제링크 : https://www.acmicpc.net/problem/2606

오늘은 백준의 단계별로 풀어보기 시리즈중 dfs와 bfs 문제 2606번을 풀었다.
컴퓨터가 연결이 되어 있다는 점과 그 연결되어 있는 컴퓨터는 바이러스가 전염이
되어 가는 과정을 넓이 탐색과 깊이 탐색의 방식으로 찾아가보며 문제를 풀었다.
연결되어 있는걸 어떻게 구현할까 한참을 고민하다 다른분이 올려둔 코드를 보고
딕셔너리를 사용하면 쉽게 해결된다는걸 알게 되었다.
처음엔 리스트를 이용하여 풀려했었는데 딕셔너리를 이용하니 아주 간단했었다.

bfs로 해결한 코드

from collections import deque
import sys
read = lambda : sys.stdin.readline().strip()

def bfs(x, y, cnt):
  dx = [1, -1, 0, 0]
  dy = [0, 0, 1, -1]

  q = deque()
  q.append([x, y])
  field[x][y] = 0
  while q:
    a, b = q.popleft()
    for i in range(4):
      nx = a + dx[i]
      ny = b + dy[i]
      if 0 <= nx < n and 0 <= ny < n and field[nx][ny] == 1:  
        field[nx][ny] = 0
        q.append([nx, ny])
        cnt += 1
  return cnt

n = int(read())

field = [list(map(int, list(read()))) for _ in range(n)]  
answer = []

for i in range(n):
  for j in range(n):
    if field[i][j] == 1:

      answer.append(bfs(i, j, 1))

print(len(answer))
answer.sort()
for i in answer:
  print(i) 

처음엔 데크를 이용하여 bfs로 문제를 먼저 해결하였다.
그리고 나서 dfs로 문제를 한번 더 풀어보았다.

dfs로 해결한 코드

import sys
read = lambda : sys.stdin.readline().strip()

n = int(read())
matrix = [list(map(int, list(read()))) for _ in range(n)]

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

def dfs(x, y, cnt):
  matrix[x][y] = 0
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < n and matrix[nx][ny] == 1:
        cnt = dfs(nx, ny, cnt + 1)
  return cnt

ans = []

for i in range(n):
  for j in range(n):
    if matrix[i][j] == 1:
      ans.append(dfs(i, j, 1))

print(len(ans))
for n in sorted(ans):
  print(n)

이번 유형의 문제는 bfs보단 dfs가 더 쉽고 빠르게 해결되는것 같다.