[Python] 프로그래머스 - 섬은 몇개일까?

[문제]

 

[풀이]

#입력과 출력을 자유롭게 작성해주세요
arr=[]

w, h = map(int, input().split())
for i in range(h):
    arr.append(list(map(int, input().split())))
    
def solution(arr, w, h):
    
    answer=0
    dh = [-1, 0, 1, 0]
    dw = [0, 1, 0, -1]
    
    def dfs(arr, x, y):
        for dir in range(4):
            new_x = x+dw[dir]
            new_y = y+dh[dir]
            if(0<=new_x<=w-1 and 0<=new_y<=h-1 and arr[new_y][new_x] == 1):
                arr[new_y][new_x] = 0
                dfs(arr, new_x, new_y)
                
    
    for i in range(h):
        for j in range(w):
            if (arr[i][j]==1):
                dfs(arr, j, i)
                answer+=1
    
    return answer
     
print(solution(arr, w, h))

 

DFS/BFS 모두 사용 가능한 문제이다. 1을 발견하면, 인접한 1을 모두 0으로 바꾸어주는 (방문 처리를 해주는) 논리를 사용한다. 따라서 인접한 1들은 한번씩 카운트 되고, 섬의 개수를 셀 수 있다. "무리지은 것들의 개수"를 찾을 때 활용할 수 있을 것 같다.

 

2차원 배열 문제는 항상 인덱스를 조심하면서 봐야 한다. 첫번째 인자가 행, 두번째 인자가 열의 값이다. 가우시안 좌표인 (x, y)라고 생각하면 [y-1][x-1]가 된다.