[백준 4963] 섬의 개수

문제

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

처음 작성한 코드

import sys
from collections import deque

def BFS(i, j):
    x = [1, 1, 1, 0, 0, -1, -1, -1]
    y = [1, 0, -1, 1, -1, 1, 0, -1]

    queue = deque()
    queue.append((i,j))

    while queue:
        now = queue.popleft()
        for i in range(8):
            next_x = now[0] + x[i]
            next_y = now[1] + y[i]
            
            if (0 <= next_x < h) and (0 <= next_y < w):
                if arr[next_x][next_y] == 1:
                    arr[next_x][next_y] = 0
                    queue.append((next_x, next_y)) 

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w * h == 0:
        break
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1:
                cnt += 1
                arr[i][j] = 0
                BFS(i,j)
    print(cnt)

1.  arr[i][j]이 1이면 섬이기 때문에 일단 갯수를 올려주고 0으로 만들고(재방문하지않기위해) 이 섬과 인접해있는 모든 섬들을 다 0으로 만들어줄거다(BFS함수내에서). 8개의 방향을 다 돌면서 1이면 queue에 넣고 그 섬과 인접한 섬을 또 queue에 넣고 이런식으로 접해있는 모든 섬을 0으로 만들면서 진행한다.

깨달은 점

• 분명 어떻게 짤지 다 알겠는데도 어떻게 짤지 모르겠다 ㅋ ㅋ 문제는 이해했는데 코드를 못짠다 -> 그럼 문제를 이해 못한겁니다 - 나OO 교수님 - . . . 새겨듣도록 하겠습니다....