백준 4963번, 섬의 개수 Python 풀이

백준 4963번, 섬의 개수 Python 풀이

문제 설명

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

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

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

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스의 첫째 줄에는 지도의 너비 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. 이차원 배열을 왼쪽 위부터 오른쪽 아래까지 순회하겠다.
2. 이차원 배열 내에 1이 있으면 탐색을 시작하겠다.
3. 8방향 탐색을 하겠다. 만약 이어진 곳(1)이라면 스택에 넣어두고 탐색을 기약한다.
4. 한 방향으로 이동했는데 또 탐색할 곳이 있으면 그것도 스택에 넣는다.
5. 스택이 다 비었으면 이제 갈 곳이 없음으로 카운트를 늘린다.
6. 2차원 배열을 다 순회할 때 까지 한다.

헷갈렸던 점

• stack에 두 가지 값을 넣으려면 STL을 사용하거나 struct를 사용해야 한다.
  → 파이썬에서는 그냥 (x, y) 튜플로 넣으면 된다.
• x, y의 값이 바뀌어있었다.
  → graph[y][x]임을 항상 기억하자.
• dx, dy를 매번 초기화해야한다.
  → 전역에서 한 번만 선언하고 재사용하자.

전체 코드 (Python)

direction1 = [-1,-1,-1,0,1,1,1,0]
direction2 = [-1,0,1,1,1,0,-1,-1]

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y

while True:
    n1,n2 = map(int,input().split())
    if n1==0 and n2==0:
        break
    arr = []
    for i in range(n2):
        arr.append(list(map(int,input().split())))
    visited = [[0]*n1 for _ in range(n2)]
    cnt=0
    for i in range(n2):
        for j in range(n1):
            if arr[i][j]==1 and visited[i][j]==0:
                stack = [Point(j,i)]
                visited[i][j]=1
                while stack:
                    p = stack.pop()
                    x = p.x
                    y = p.y
                    for k in range(8):
                        nx = x+direction1[k]
                        ny = y+direction2[k]
                        if 0<=nx<n1 and 0<=ny<n2:
                            if arr[ny][nx]==1 and visited[ny][nx]==0:
                                visited[ny][nx]=1
                                stack.append(Point(nx,ny))
                cnt+=1
    print(cnt)