[Baekjoon/🥈SilverⅡ] 4963: 섬의 개수

Intro

접근 방법🙋‍♀️

• 해당 문제는 단순히 상하좌우만이 아닌 대각선까지 포함해 bfs, dfs를 적용하는 문제이다.

• 행렬로 주어지는 그래프에서 대각선, 상하좌우를 모두 확인하기 위해서는 다음의 배열들이 필요하다.

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

Algoritm👩‍💻: BFS

• 우선 BFS를 적용해 문제를 해결해보자.

# 21.01.10
# 4963: 섬의 개수

import sys

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

def bfs(i, j):
  lst[i][j] = 0
  queue = [[i, j]]
  while queue:
    a, b = queue[0][0], queue[0][1]
    del queue[0]
    for k in range(8):
      x = a + dx[k]
      y = b + dy[k]
      if 0 <= x < h and 0 <= y < w and lst[x][y] == 1:
        lst[x][y] = 0
        queue.append([x, y])

      

while 1:
  w, h = map(int, sys.stdin.readline().rstrip().split())
  if w == 0 and h == 0:
    break

  lst = []
  for i in range(h):
    lst.append(list(map(int, sys.stdin.readline().rstrip().split())))

  cnt = 0
  for i in range(h):
    for j in range(w):
      if lst[i][j] == 1:
        bfs(i, j)
        cnt += 1

  print(cnt)
  

• 모든 행렬을 돌며 1인 요소에 대해서 BFS를 호출한다.

• BFS 함수에서는 해당 요소의 대각선, 상하좌우에 존재하는 요소들 중 값이 1인 요소들을 차례로 queue에 넣으면서 그 값들을 0으로 바꾼다.

  • 1인 요소의 대각선, 상하좌우에 있는 값이 1인 요소들은 하나의 섬으로 취급되기 때문이다.

  • BFS에서 반환된 후, 섬의 개수를 하나 증가시켜준다.

• 모든 요소들을 순환한 후, 섬의 개수를 출력한다.

Algoritm👩‍💻: DFS

• 이번에는 해당 문제를 DFS를 통해서 해결해보자.

# 21.01.10
# 4963: 섬의 개수

import sys
sys.setrecursionlimit(10000)

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

def dfs(i, j):
  lst[i][j] = 0
  for k in range(8):
    x = i + dx[k]
    y = j + dy[k]
    if 0 <= x < h and 0 <= y < w and lst[x][y] == 1:
      dfs(x, y)

      

while 1:
  w, h = map(int, sys.stdin.readline().rstrip().split())
  if w == 0 and h == 0:
    break

  lst = []
  for i in range(h):
    lst.append(list(map(int, sys.stdin.readline().rstrip().split())))

  cnt = 0
  for i in range(h):
    for j in range(w):
      if lst[i][j] == 1:
        dfs(i, j)
        cnt += 1

  print(cnt)

→ 잠깐🔔: ‘sys.setrecursionlimit(10000)’

• 파이썬은 기본 재귀 깊이 제한이 1000으로 매우 얇다.

• 재귀를 사용해 푸는 문제일 경우, 위 코드를 통해 재귀 제한에 걸리지 않도록 해야 한다!!

• 모든 행렬을 돌며 1인 요소에 대해서 DFS를 호출한다.

• DFS 함수에서는 해당 요소의 값을 0으로 바꾼 후, 대각선과 상하좌우에 있는 요소들 중 값이 1인 요소들에 대해서 DFS를 재귀 호출한다.

• 모든 요소들을 순환한 후, 섬의 개수를 출력한다.

참고📃

• https://fuzzysound.github.io/sys-setrecursionlimit
• https://velog.io/@hamfan524/%EB%B0%B1%EC%A4%80-4963%EB%B2%88-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC
• https://pacific-ocean.tistory.com/273

그럼!! 이번 포스팅은 여기서!

끝!! ~(˘▾˘~)