[백준4963] 섬의 개수

문제

---

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

생각의 흐름

---

인접한 곳들을 탐색하여 그룹을 짓는 문제이다.

특이한 점은 일반적인 상하좌우 이외에도 대각선 4곳까지도 인접한 영역으로 본다는 것이다.

다시말해, 아래의 경우에서 가운데의 1과 인전한 곳은 노랑색으로 표시된 8개의 영역이다.

 

0	0	1
1	1	0
0	0	0

 

이 때, 문제가 되는 것은 귀퉁이의 원소들을 검사할 때이다. 이를 해결하기 위해 아래와 같이 배열의 가장자리에 0으로 채워진 행과 열을 추가해준다.

 

0	0	0	0	0
0	0	0	1	0
0	1	1	0	0
0	0	0	0	0
0	0	0	0	0

 

깨달은 점

---

• 리스트의 값을 줄 때 파이썬에서는 list1 = list2[:]라고 해주어야 reference by value가 된다!!! 실수로 list1 = list2라고 하면 reference by address가 되어 list1의 값을 바꿀 때마다 list2의 값도 같이 갱신되어버림.
• 파이썬에는 재귀함수의 최대호출 깊이가 정해져있다.(왜그런지는 모르겠지만 그래서 C++로 짠 DFS, BFS 코드의 경우 무리 없이 돌아가는데 파이썬에서는 런타임에러 시간초과가 나는 경우가 많다.) 이를 해결하기 위해선 sys.setrecursionlimit()함수를 이용해 최대호출깊이를 설정해주어야 한다. 
• 이 외에도 파이썬을 사용하여 문제를 풀 때 주의할 점들이 많은데 잘 정리되어 있는 다음의 블로그를 참고하기 바란다.  

https://dailyheumsi.tistory.com/32

파이썬으로 문제 풀 때 주의해야할 점들

 

코드

---

import sys

M,N = 0, 0
arr = []
cnt = 0

def dfs(x,y):
    arr[x][y]=0
    if arr[x - 1][y] == 1:
        dfs(x - 1, y)
    if arr[x + 1][y] == 1:
        dfs(x + 1, y)
    if arr[x][y - 1] == 1:
	    dfs(x, y - 1)
    if arr[x][y + 1] == 1:
	    dfs(x, y + 1)
    if arr[x-1][y-1] == 1:
        dfs(x-1, y-1)
    if arr[x-1][y+1] == 1:
        dfs(x-1, y+1)
    if arr[x+1][y-1] == 1:
        dfs(x+1, y-1)
    if arr[x+1][y+1] == 1:
        dfs(x+1, y+1)

    return


if __name__=='__main__':
    sys.setrecursionlimit(10**8)
    while True:
        cnt = 0
        input_arr = []
        M,N = map(int, sys.stdin.readline().split())
        if M==0 and N==0:
            break
        temp = []
        for _ in range(M+2):
            temp.append(0)
        for _ in range(N+2):
            # 리스트를 복사해주어야 함!!! ref by value
            arr.append(temp[:])


        for _ in range(N):
            input_arr.append(list(map(int, sys.stdin.readline().split())))

        for i in range(N):
            for j in range(M):
                arr[i+1][j+1] = input_arr[i][j]        

        for i in range(1, N+1):
            for j in range(1, M+1):
                if arr[i][j] == 1:
                    dfs(i,j)
                    cnt += 1

        print(cnt)
        del arr[:]