작심큰일 챌린지 - Day 7. 섬의 개수 (미들러, Python)

출처 - 작심큰일 챌린지 메인 페이지

 

7일 차가 시작됐다.

 

이제 매일 아침에 알고리즘 문제를  푸는 것이 어색하지 않아서 뭔가 기분이 좋다.

---

Day 7. 섬의 개수

 

오늘의 문제는 백준 프로그래밍 4963번 문제다.

 

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

 

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스의 첫째 줄에는 지도의 너비 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

 

 

---

풀이 과정

 

먼저 알고리즘 구현의 순서를 생각해 보았다.

 

1. 데이터 입력 기반 W×H 지도 그리기 (0 0 입력 시 종료)
2. 지도 탐색 (BFS vs. DFS)
3. DFS/BFS로 섬의 연결 부분(상하좌우 + 대각선) 모두 방문 처리 (이때, 섬의 count +1)

 

입력값이 0 0 일 때까지 반복

 

사실 가장 기본적으로 생각나는 원시적인 방식이 있었다. 바로 while 문을 활용하는 방식이다.'

 

import sys
input = sys.stdin.readline

while True:
    W, H = map(int, input().split())

    if W == 0 and H == 0:
        break

    print(W, H)

 

하지만 위 방식이 가장 효율적이라는 생각은 들지 않았다.

 

EOF를 고려해야 하는 환경에서는 try/except가 필요하기 때문인데, 우리는 Python에서 이를 쉽게 보완하는 for line in sys.stdin 방식을 알고 있다.

 

import sys

for line in sys.stdin:
    W, H = map(int, line.split())

    if W == 0 and H == 0:
        break
        
    print(W, H)

 

코드도 더 깔끔하고, 대량입력에도 더 유리하다. 쓰지 않을 이유가 없다.

 

대각선을 고려한 DFS

 

처음에는 대각선을 고려하기 위해서 DFS에 추가적인 조치가 필요한가 했다.

 

    def dfs(x,y):
        board_map[x][y] = 0
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and board_map[nx][ny] == 1:
                dfs(nx, ny)

 

하지만 일반적으로 우리가 사용하는 dfs의 상하좌우 비교 방식을 그대로 사용해도 상관없었다.

 

단, directions에 대각선에 대한 시나리오를 추가해줘야 했다.

 

directions = [(-1,0),(1,0),(0,-1),(0,1), (-1,-1),(-1,1),(1,-1),(1,1)]

 

조건이 같아도 상관없는 이유는 다음과 같다:

 

1. nx, ny는 현재 좌표 (x, y)에서 directions에 있는 (dx, dy)를 더해서 만든 다음 탐색 좌표
2. 4방향이든 8방향이든, 새로 이동한 좌표가
   • 지도 범위 안에 있어야 하고 (0 <= nx < H / 0 <= ny < W)
   • 아직 방문하지 않은 땅이어야 함 (board_map[nx][ny] == 1)

---

 

개선점

Generated by ImgFlip

 

이런 좌표(nx, ny, directions) 유형의 문제는 통상 써오던 방식대로 코드를 구성했다.

 

하지만 "왜 이렇게 쓰는가"에 대한 통찰이 모자랐던 것 같다.

 

dfs 함수 정의 시 헷갈렸던 부분이, 노드 기반의 탐색은 visited를 쓰는데 왜 2차원 배열에서 상하좌우(+대각선)를 비교할 때는 방문한 곳을 0으로 처리하는지 깊게 생각해보지 못했었다. 

 

해당 과정이 방문처리 최적화의 방법이라는 것을 생각하지 못하고 사용했다. 별도 visited 배열을 생성하지 않는 것이 메모리 절약에 유리하다는 점을 생각하지 못하고 있었다.

 

추가로, 아직 dfs/bfs를 block 단위로 외우지는 못하고 있어서 이 부분에 대한 연습이 더 많이 필요하다는 생각이 들었다.