J2KB 3기 서브젝트 4주차 (1) 섬의 개수

4주차

백준 4963번 섬의 개수

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

💡 풀이 전 계획과 생각

• 땅이 1, 0이 바다라 했으니 주변 탐색을 하며 1을 찾아 개수를 세야겠구나
  + 방향 선언 후 dfs / bfs를 이용하자!

💡 풀이

# bfs로 풀어보기
from collections import deque
import sys
input = sys.stdin.readline

def bfs(x, y):
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, -1), (-1, 1)]

    que = deque()
    que.append((x, y))

    island[x][y] = 0

    while que:
        n = que.popleft()

        for i in range(8):
            nx = n[0] + directions[i][0]
            ny = n[1] + directions[i][1]

            if (0<=nx<h) and (0<=ny<w):
                if int(island[nx][ny]) == 1:
                    island[nx][ny] = 0
                    que.append((nx, ny))

while True:
    w, h = map(int, input().split())
    cnt = 0
    if w == 0 and h == 0:
        break
    # 입력에서 띄어쓰기 제거하고 행렬 만들기
    island = [' '.join(input()).split() for _ in range(h)]
    # print(island)

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

    print(cnt)

🧐 막혔던 점과 고민

• 주어진 인풋 양식에 띄어쓰기가 들어가 입력 후 바로 그래프를 생성하는 데 난관 봉착

👏🏻 알게된 개념과 소감

• join 함수를 통해 input 사이의 띄어쓰기 제거 후 그래프 생성 가능
  + 단, join은 string 형식을 사용하는 함수기 때문에, 후에 쓸 때 타입을 유의해야한다.
• 대각선까지 탐방할 경우 : 방향이 4개에서 8개로 증가
  + dx, dy 리스트 선언 대신 튜플을 담은 direction 리스트 생성 후 활용
  

❗️ 개인적으로 dfs / bfs에서 반복문이 어떻게 쓰이는지, 어느 범위를 탐색해야하는 지
자세하게 알아보기 좋은 문제였다고 생각한다.

💡 요약

while que:
        n = que.popleft()

        for i in range(8):
            nx = n[0] + directions[i][0]
            ny = n[1] + directions[i][1]

            if (0<=nx<h) and (0<=ny<w):
                if int(island[nx][ny]) == 1:
                    island[nx][ny] = 0
                    que.append((nx, ny))