[백준] 섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

학교 과제때문에 풀어봤다.

자료구조 시간에 풀어본 문제라서 스택을 이용하여 dfs로 풀려고 하였는데

찾아보니깐 큐를 이용하여 bfs로 푸는 방법이 있어서 그 방법을 취하였다.

 

 

스택을 이용하는 경우에는, 1을 따라서 계속해서 한 곳만 팠다. 그리고 한 쪽을 다 파고 나면 다시 뒤로 가기 뒤로 가기 뒤로 가기 파지 않은 곳 찾아보기로 문제를 해결했다. 스택은 가장 최근에 들어간 원소를 꺼내기 때문에 초반에 넣은 것을 계속 뒤로 미루었다.

 

큐를 이용하는 경우에는 주변을 다 섭렵하면서 팠다. 여기 갔다가 다시 저기 갔다가 여기 저기 움직였다. 새로운 걸 담아도 다시 가장 먼저 넣었던 것을 꺼내기 때문이다. 새로운 걸 담고 가장 먼저 넣었던 것을 빼는 작업을 반복해서 여기 저기 움직였다.

 

 

섬의 개수 문제 풀이초안

 

1. 모든 원소를 다 돌아다닌다. -> 이중 반복문

 

2. 돌아다니다가 섬을 만나면 섬을 샅샅이 뒤진다 -> bfs 방법

현재 위치에서 다음 위치를 살펴본다. (방문한 적이 있는가? 섬/바다 인가?)

bfs라서 우선 주위를 모두 살펴본다. -> pop해주고 주위 원소를 반복문으로 돌면서 다 push 반복!

그럼, dfs는? pop해주고 다음 원소의 가능성보고 가능성 있으면 지금것 push로 기록 남겨두고 다음 걸로 넘어가서 또 주위 살펴보다가 가능성있으면 지금 꺼 push하고 또 다음으로 넘어가서 주위보는데 주위에 없으면 pop해서 이전에 이력으로 다시 넘어간다.

 

 

3. 섬을 다 돌고나면 다시 윗 과정으로 반복하기 끝나면, 섬개수 출력

 

 

 

 

 

from collections import deque

land = [
    [1,1,1,1,0],
    [1,1,0,1,0],
    [1,1,0,0,0],
    [0,0,0,0,0]
]


direction = [
    [-1,0],
    [0,1],
    [1,0],
    [0,-1]
]

q = deque()
row_length = len(land)
col_length = len(land[1])
land_cnt = 0


for i in range(row_length):
    for j in range(col_length):
        if land[i][j] == 1:
            q.append([i,j])
            land[i][j] = 0
            
            while q:
                current = q.popleft()
                for k in range(len(direction)):
                    new_x =  current[0] + direction[k][0]
                    new_y =  current[1] + direction[k][1]
                    
                    if 0 <= new_x < col_length and 0 <= new_y < row_length:
                        if land[new_x][new_y] == 1:
                            q.append([new_x,new_y])
                            land[new_x][new_y] = 0
            land_cnt += 1

print("섬은",land_cnt,"개 있습니다.")

 

 

 

 

추가알고리즘----

 

union find algorithm

 

8개의 객체에서 집합으로 묶어주는 과정을 거친다.

depth가 2인 트리를 만든다.

그럼 섬의 개수는 루트의 개수만 세주면 된다.

결국 여기에도 bfs과정을 거친다.