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

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

dfs와 bfs 두가지 방법 다 사용하여 풀어보았다.
처음 dfs와 bfs문제를 풀기 시작했을땐 어떻게 접근해야하며 해결해야할지
도저히 감이 오지 않았었는데, 다양한 문제들을 풀어보고 모르면 다른분들의
코드를 보며 분석을 하는 공부를 계속하다 보니 이젠 dfs나 bfs 문제들은 처음보는 경우에도
간단하게 풀 수 있게 되었다.

dfs를 이용하여 푼 코드

import sys
read = sys.stdin.readline
sys.setrecursionlimit(10000)

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

  field[x][y] = 0
  for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < h and 0 <= ny < w and field[nx][ny] == 1:
      dfs(nx, ny)

while True:
  w, h = map(int, read().split())
  if w == 0 and h == 0:
    break
  field = []
  count = 0
  for _ in range(h):
    field.append(list(map(int, read().split())))
  for i in range(h):
    for j in range(w):
      if field[i][j] == 1:
        dfs(i, j)
        count += 1
  
  print(count)

이번 문제는 대각선에 있는 값도 찾아가는 걸 구현하는 것만 할 수 있다면
다른문제들과 거의 다른 점이 없었다.
dx와 dy에 대각선도 추가해주는게 해결점이었다.

bfs를 사용하여 푼 코드

from collections import deque
import sys
read = sys.stdin.readline

def bfs(x, y):
  dx = [1, -1, 0, 0, 1, -1, 1, -1]
  dy = [0, 0, -1, 1, -1, 1, 1, -1]
  field[x][y] = 0
  q = deque()
  q.append([x, y])
  while q:
    a, b = q.popleft()
    for i in range(8):
      nx = a + dx[i]
      ny = b + dy[i]
      if 0 <= nx < h and 0 <= ny < w and field[nx][ny] == 1:
        field[nx][ny] = 0
        q.append([nx, ny])

while True:
  w, h = map(int, read().split())
  if w == 0 and h == 0:
    break
  field = []
  count = 0
  for _ in range(h):
    field.append(list(map(int, read().split())))
  for i in range(h):
    for j in range(w):
      if field[i][j] == 1:
        bfs(i, j)
        count += 1
  print(count)

항상 풀땐 습관적으로 bfs로 먼저 풀고 dfs로 다시 푸는데
두가지 방법 다 장단점이 있어 꼭 문제를 두개다 이용해서 풀어보는게 좋은 것 같다.