S2 4963. 섬의 개수

문제 보기 :  4963번: 섬의 개수

---

문제

• 정답률 : 49%

---

작성 코드

from collections import deque  

# 8방향 탐색을 위한 방향 벡터 정의 (상하좌우+대각선)
directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, 1), (1, -1), (-1, -1)]

# 섬 탐색 함수 정의 (BFS 사용)
def island(graph, start):
    graph[start[1]][start[0]] = 0  # 시작점을 방문 처리 (0으로 설정)
    visited[start[1]][start[0]] = True  # 방문 여부 기록
    count = 1  # 섬 크기(1의 개수) 카운트

    dd = deque([start])
    while dd:  # BFS 탐색
        ww, hh = dd.popleft()  # 현재 위치
        for dw, dh in directions:  # 8방향 탐색
            neww = ww + dw  ; newh = hh + dh  # 새로운 가로/세로 위치
            # 새로운 위치가 유효하고, 방문하지 않았으며 섬인 경우
            if 0 <= neww < w and 0 <= newh < h and graph[newh][neww] != 0 and not visited[newh][neww]:
                graph[newh][neww] = 0  # 방문 처리
                visited[newh][neww] = True  # 방문 여부 기록
                dd.append((neww, newh))  # 다음 탐색 대상으로 추가
                count += 1  # 섬 크기 증가
    return count  # 섬 크기 반환

while True:
    # 지도 크기 입력받음 (w: 너비, h: 높이)
    w, h = map(int, input().split())
    if w == 0 and h == 0:  # 입력 종료 조건
        break

    graph = [list(map(int, input().split())) for _ in range(h)] # 지도 입력받음
    visited = [[False] * w for _ in range(h)]  # 방문 여부 초기화

    answer = []  # 섬 크기 저장 리스트
    dd = deque()  # BFS를 위한 deque 초기화
    
	# 전체 지도 탐색
    for hh in range(h):  
        for ww in range(w):
            if graph[hh][ww] == 1:  # 섬 발견 시
                answer.append(island(graph, (ww, hh)))  # 섬 탐색 및 크기 추가

    print(len(answer))  # 발견된 섬의 개수 출력

---

풀이

이 문제는 2667번: 단지번호붙이기와 비슷하다.

그런데 이 문제가 조금 더 어렵게 느껴진 이유를 꼽자면, 첫 번째로 대각선 방향도 고려해야 한다는 점이다.
단지번호붙이기에서는 상하좌우 4방향만 체크하면 됐지만, 여기서는 대각선 방향까지 포함해 8방향을 탐색해야 한다.
그래서 directions에 [(1,1), (-1,1), (1,-1), (-1,-1)] 같은 대각선 방향도 추가해야 한다.

두 번째 이유는 늘 헷갈리는 [x][y]인지 [y][x]인지 구분하는 과정이다.
deque에 값을 넣고 빼는 순서와 2차원 리스트에서 인덱스를 접근하는 순서가 다르다 보니,
멍때리고 풀다 보면 에러가 와르르 쏟아질 수 있다. 가로와 세로를 헷갈리지 않도록 신경 써야 한다.

그리고 내가 풀이한 코드에서 주의해야 할 점은 count 변수가 섬의 개수가 아니라, 한 섬의 면적을 나타낸다는 점이다.
그래서 만약 문제에서 각 섬의 면적을 계산해서 출력하라고 했다면, 이 코드 그대로 사용해도 바로 답을 출력할 수 있다.