백준 4963 - 파이썬

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

문제 풀이

기본적인 BFS 풀이 방식에 대각선으로 이동하는 것만 생각하면 쉽게 풀 수 있는 문제이다. 주의할 점은 w와 h의 순서를 잘 생각해 줘야 인덱스의 범위를 벗어나지 않는다.

 

BFS 풀이

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

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

def bfs(x, y):
  q = deque()
  q.append((x, y))
  visited[x][y] = True
  graph[x][y] = 0

  while q:
    x, y = q.popleft()

    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or nx >= w or ny < 0 or ny >= h:
        continue

      if graph[nx][ny] == 0:
        continue
      
      if graph[nx][ny] == 1 and not visited[nx][ny]:
        q.append((nx, ny))
        visited[nx][ny] = True
        graph[nx][ny] = 0

result = []

while True:
  h, w = map(int, input().split())

  if h == 0 and w == 0:
    break

  graph = [list(map(int, input().split())) for _ in range(w)]
  visited = [[False] * h for _ in range(w)]
  
  cnt = 0
  
  for i in range(w):
    for j in range(h):
      if graph[i][j] == 1:
        bfs(i,j)
        cnt += 1

  result.append(cnt)

for i in result:
  print(i)

 

DFS 풀이

import sys
input = sys.stdin.readline

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

def dfs(x,y):
  graph[x][y] = 0

  for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0 <= nx < w and 0 <= ny < h and graph[nx][ny] == 1:
      dfs(nx,ny)

result = []

while True:
  h, w = map(int, input().split())

  if h == 0 and w == 0:
    break

  graph = [list(map(int, input().split())) for _ in range(w)]
  
  cnt = 0
  
  for i in range(w):
    for j in range(h):
      if graph[i][j] == 1:
        dfs(i,j)
        cnt += 1

  result.append(cnt)

for i in result:
  print(i)

 

이런 문제는 이제 다른 사람의 풀이를 찾아보지 않아도 풀 수 있는거 같다. 발전한게 느껴져서 뿌듯하고 더 열심히 해야 되겠다.