코딩 챌린지 2일차 : 4963번 섬의 개수(S2)

4963 : 섬의 개수 - 문제 링크

1. 문제 탐색하기

입력

w, h 지도의 너비, 높이
land[w][h] 지도

알고리즘 설계

하나의 1로부터 진행 가능 경로 계속 탐색 -> DFS 사용
(*DFS나 BFS나 비슷한 효율을 낼 것 같아 개인적으로 익숙한 DFS 사용)
진행 가능 경로가 없다면 새로운 1(섬)을 찾아 다시 DFS 탐색
DFS 실행 수가 곧 섬의 개수 (구하고자 하는 것)

시간복잡도

그래프 전부를 탐색, 하나의 노드에서 8개의 방향을 탐색 :
8 $*$ O(w $*$ h) -> $O(n^2)$
1 $\leq$ w, h $\leq$ 50 -> w $*$ h $\leq$ 2500이므로 20,000번의 연산 수행 => 통과 가능

2. 코드 설계하기

• 반복문이 많아 pseudo code로 작성

while True:
	w,h input 받기
	w,h가  0 0이면: break
    land input 받기
    land의 모든 항목에 대해:
        1 찾으면:
            섬 += 1
            방문한 항목의 value는 0으로 수정 (visited 대체)
            stack에 push
            stack이 차있을 동안 DFS 진행
   	print 섬

3. 시도 회차 수정 사항

1회차) 한 번만에 짜릿한 성공!

4. 정답 코드

import sys
input = sys.stdin.readline

# 상하좌우 대각선 방향 배열
dx = [0, 0, 1, -1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, 1, 1, -1, -1]

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break                             # 프로그램 종료

    land = []
    result = 0                                              # 섬의 개수

    for _ in range(h):
        land.append(list(map(int, input().split())))

    for i in range(h):                                      # y
        for j in range(w):                                  # x
            
            # 새 섬 발견
            if land[i][j] == 1:
                result += 1
                land[i][j] = 0                              # visited 대체
                stack = [[i, j]]
                
                # DFS
                while stack:
                    y, x = stack.pop()
                    for k in range(8):                      # 8방향 탐색
                        nx, ny = x + dx[k], y + dy[k]
                        if -1 < nx < w and -1 < ny < h:     # out of index 방지
                            if land[ny][nx] == 1:
                                land[ny][nx] = 0
                                stack.append([ny, nx])
    print(result)

반복문 투성이인 이번 코드... 개인적으로는 함수 작성하는 걸 별로 좋아하지 않는데 이정도로 들여쓰기 파티일 줄 알았으면 함수를 작성할 걸 그랬다. 😅 아직 시간복잡도 계산은 너무 어려워😭

5. 해설지 참고 후

• [ TIP ] 테스트 케이스의 개수는 명시되지 않았지만, 백준 문제에서 테스트케이스의 개수는 해당 풀이가 정답이라면 시간 안에 통과할 수 있는 수준으로 제공

오늘은 함수 구현의 차이를 제외하고는 멘토님과 변수명도 그렇고 거의 동일한 코드였다. 짱신기뿌듯함. 그래도 문제 탐색, 코드 설계 부분은 많이 보고 배워야겠다. 남이 봐도 이해할 수 있도록 상세하게 작성하기!