BOJ-백준 4963번 섬의 개수

BOJ-백준 4963번 섬의 개수

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

4963번: 섬의 개수

 

 

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

 

✅ Python 정답 코드 입니다.

 

import sys
sys.setrecursionlimit(10**6)

def dfs(i,j):
  if i<0 or j<0 or i>=h or j >=w:
    return
  if field[i][j] == 0:
    return
  field[i][j] = 0
  # 상하좌우 이동
  dfs(i,j-1)
  dfs(i,j+1)
  dfs(i-1,j)
  dfs(i+1,j)
  #대각선 이동
  dfs(i+1,j-1)
  dfs(i+1,j+1)
  dfs(i-1,j-1)
  dfs(i-1,j+1)
  return
island_list = []
while 1:
  w, h = map(int, input().split())
  if w==0 and h==0:
    break

  field = []
  for _ in range(h):
    x = list(map(int, input().split()))
    field.append(x)

  island = 0
  for i in range(h):
    for j in range(w): 
      if field[i][j] == 1:
        dfs(i,j)
        island +=1
  island_list.append(island)
for i in island_list:
  print(i)

📌 해설

DFS를 수행해 graph를 탐색합니다. 인접한 땅들을 dfs로 탐색하여 섬의 수를 증가시킵니다. 

🚩 주의

상하좌우, 대각선 방향, 총 8번의 dfs를 수행해야 합니다. 

 

def dfs(i,j):
  if i<0 or j<0 or i>=h or j >=w:
    return
  if field[i][j] == 0:
    return
  field[i][j] = 0
  # 상하좌우 이동
  dfs(i,j-1)
  dfs(i,j+1)
  dfs(i-1,j)
  dfs(i+1,j)
  #대각선 이동
  dfs(i+1,j-1)
  dfs(i+1,j+1)
  dfs(i-1,j-1)
  dfs(i-1,j+1)
  return

1. 상하좌우, 대각선 방향을 이동하는 dfs를 작성합니다. 

1-1. field를 벗어나는 좌표를 받을 경우 dfs 탐색을 종료합니다.

1-2. field가 바다(0)면, dfs 탐색을 종료합니다. 

1-3. field가 땅(1)이면, 방문표시를 합니다. (1->0)

1-4. 상하좌우, 대각선 방향을 이동하는 dfs를 재귀호출 합니다.

 

island_list = []
while 1:
  w, h = map(int, input().split())
  if w==0 and h==0:
    break

  field = []
  for _ in range(h):
    x = list(map(int, input().split()))
    field.append(x)

2. 섬과 바다의 정보가 주어진 지도(field)를 입력받습니다. 

2-1. w : 지도 너비, h : 지도 높이, island_list: 모든 지도의 섬의 개수를 저장할 리스트 변수

2-2. 만약 지도 너비, 지도 높이를 0 0 으로 입력 받으면 while문을 종료 합니다.

2-3. 지도 정보를 입력 받습니다. 

 

  island = 0
  for i in range(h):
    for j in range(w): 
      if field[i][j] == 1:
        dfs(i,j)
        island +=1
  island_list.append(island)

for i in island_list:
  print(i)

3. field를 모두 조회하는 이중 for문을 작성합니다. 

3-1. island : 각 지도의 섬의 개수

3-2. field에서 섬(1)이 발견되면  dfs 탐색을 시작합니다.

3-3. dfs 탐색이 종료되면  섬의 개수(island)를 하나 증가 시킵니다. 

3-4. field를 모두 조회하는 for문이 종료되면 섬의 갯수를 island_list에 append하여 저장합니다. 

 

모든 지도(field)를 탐색하고 나면 island_list에 저장된 섬의 개수를 차례로 출력합니다. 

 

::