[BEAKJOON] 백준 2667 - 단지번호붙이기

 

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

2667번: 단지번호붙이기

 

 

 

---

DFS - 깊이 우선 탐색

- Root node 나 다른 임의의 node에서 다음 분기로 넘어가기 전에 해당 분기를 완벽히 탐색하는 방법이다.

Stack 혹은 재귀함수(Recursion)으로 구현된다.

- 경로를 탐색하고 한 방향으로 갈 때까지 가고 안되면 다른 방향으로 다시 탐색

- 모든 노드를 방문하는 경우

 

시간 복잡도

( V : 접점, E : 간선 )

- 인접 리스트 : O ( V + E )

- 인접 행렬 : O ( V^2 )

 

BFS - 너비 우선 탐색

- Root node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법

- Queue를 사용해서 구현

 

시간 복잡도 

( V : 접점, E : 간선 )

- 인접 리스트 : O ( V + E )

- 인접 행렬 : O ( V^2 )

 

BFS로 효과적으로 풀 수 있는 문제란?

1. 최소 비용 문제

2. 간선의 가중치가 1

3. 정점과 간선의 개수가 적음

 

판단 방법은?

DFS 

1. 모든 노드를 확인해야 할 경우

2. 경로의 특징을 저장해야 할 경우 (서로 다른 가중치를 가지고 있거나, 제약이 있을때)

 

BFS

1. 최단 거리

2. 임의의 경로 찾기 (미로 탐색 등)

 

---

 

python 에서 deque는 스택과 큐의 기능을 모두 가진 객체로, 출입구를 양쪽에 가지고 있다.

스택 : append(), pop()

ex>

a, b, c 

append('d')

==>  a, b, c, d

pop()

==> d

 

큐 : appendleft(), pop(), append(), popleft()

ex>

a, b

appendleft('d')

==> d, a, b

pop()

==> b

 

---

 

그럼 이 문제는?

모든 아파트를 다 돌면서 단지로 묶어야 한다.

붙어있는 아파트들끼리 단지로 묶이기, 방향 배열로 주변 탐색 필요

각 단지에 속하는 집의 수를 담아, 오름차순으로 정렬해서 출력

 

전형적으로 DFS, BFS 문제로 두 가지 방법 모두 풀 수 있다.

 

1. BFS

그래프 탐색 시작점을 모르기 때문에, 전체를 돌아 1인 지점에서 탐색 시작

탐색 하면서 1인 부분은 0으로 바꿔 다시 방문하지 않도록 한다.

한번의 BFS가 끝나면, 마을 하나 탄생

 

BFS로 해결한 코드는 다음과 같다.

from collections import deque

dx = [0, 0, 1, -1]

dy = [1, -1, 0, 0]

def bfs(graph, m_i, m_j):

    max_len = len(graph)

    queue = deque()

    queue.append((m_i, m_j))

    #queue.append([m_i, m_j])

    graph[m_i][m_j] = 0

    m_count = 1

    while queue:

        x, y = queue.popleft()

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if nx < 0 or nx >= max_len or ny < 0 or ny >= max_len:

                continue

            if graph[nx][ny]:

                graph[nx][ny] = 0

                queue.append((nx, ny))

                m_count += 1

    return m_count

num = int(input())

graph = []

for i in range(num):

    graph.append(list(map(int, input())))

count = []

for i in range(num):

    for j in range(num):

        if graph[i][j] == 1:

            count.append(bfs(graph, i, j))

count.sort()

print(len(count))

for i in range(len(count)):

    print(count[i])

 

 

 

2. DFS

그래프의 탐색 시작점을 모르기 때문에 동일하게 전체를 돌면서 탐색을 시작하는데,

BFS와의 차이점은 큐 대신 재귀를 사용하는 것입니다.

 

global 

Python 에서 함수 내부에서 전역 변수를 사용하기 위해서는 global 키위드를 사용하여 해당 전역 변수를 재선언해야 된다고 한다. 그렇지 않으면 지역 변수로 취급이 된다.

 

dx = [0, 0, 1, -1]

dy = [1, -1, 0, 0]

num = int(input())

graph = []

def dfs(m_x, m_y):

    if m_x < 0 or m_x >= num or m_y < 0 or m_y >= num:

        return False

    

    if graph[m_x][m_y] == 1:

        global count

        count += 1

        graph[m_x][m_y] = 0

        for i in range(4):

            nx = m_x + dx[i]

            ny = m_y + dy[i]

            dfs(nx, ny)

        return True

    return False

for i in range(num):

    graph.append(list(map(int, input())))

count = 0

result_number = []

for i in range(num):

    for j in range(num):

        if dfs(i, j) == True:

            result_number.append(count)

            count = 0

result_number.sort()

print(len(result_number))

for i in range(len(result_number)):

    print(result_number[i])

 

 

 

 

 

출처 : https://developer-mac.tistory.com/64