문제

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

입력 예시 1

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

출력 예시 1

0
1
1
3
1
9

문제 이해

아마 이렇게 시뮬레이션과 DFS/BFS가 합쳐진 문제는 map의 크기가 1000*1000정도로 제한되어 있을거다. 2차원 배열을 이용해야하기 때문이다. 이번 문제는 크게 어려울게 없다. 2차원 리스트를 돌면서 1을 발견하면 메인에서 DFS 돌린다. 메인에서 DFS를 돌리면 그와 인접한 섬들은 모두 방문처리 되므로 메인에서 호출할때 cnt를 1씩 증가한다. visited를 사용하는 대신 방문한 map의 1값을 0으로 바꾸어줘서 방문처리를 대신한다.

비슷한 유형과 다를 거라고는 테스트케이스가 "0 0"이 입력될때까지 반복된다는 것과 방향이 8가지라는 것 뿐이다.

이제는 DFS와 시뮬레이션에 익숙해져서 오류없이 한번에 코드 작성이 가능하다.

코드

# 백준 4963번 섬의 개수

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def DFS(y, x):
    global world_map
    world_map[y][x] = 0

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

        if 0 <= new_x < w and 0 <= new_y < h and world_map[new_y][new_x]:
            DFS(new_y, new_x)

# 뱡향벡터 정의 12시방향부터 시계방향[8가지]
dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

# 반복문에 들어가기 위해 초기값 할당
w, h = 1, 1

while w != 0 and h != 0:


    # 0. 입력 및 초기화
    w, h = map(int, input().split()) #너비w 높이h

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

    world_map = []
    cnt = 0

    # 1. 연결 요소 입력
    for i in range(h):
        world_map.append(list(map(int, input().split())))
    
    # 2. DFS 호출
    for i in range(h):
        for j in range(w):
            if world_map[i][j]:
                DFS(i, j)
                # 메인에서 한번 호출되면 섬하나로 카운트
                cnt += 1
    

    # 3. 출력
    print(cnt)