Algorithm/Baekjoon

[Beakjoon, Python] 2667번 : 단지번호붙이기

JMcunst 2021. 3. 4. 12:07
728x90
반응형

도입

백준 단계별 풀기 DFS와 BFS 세 번째 문제이다.

백준 2667번 문제, 입력, 출력

백준 2667번 입출력 예제 1

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

풀이

1. dx, dy라는 것을 두어 상,하,좌,우를 표현하는 것이 이번 문제의 포인트다! 이전의 바이러스 문제 등을 보면, 해당 노드에 방문만 하면 visit_list를 count하여 계산을 하였다. 하지만, 지금은 좌표 문제로 접목시키면서, 매개변수로 노드정보를 넘기는 것이 아닌 x,y좌표를 넘김으로써, 문제를 풀어나간다. 생각보다 많은 해당 문제에서 dx, dy로 상하좌우를 표현하는 것을 확인할 수 있다.

 

2. 재귀함수로 dfs를 구현하는데, 방문한 곳은 0으로 만들어 줘서, 재방문을 막아준다. 

코드

from sys import stdin

dx=[-1,0,1,0] # 좌 우 위 아래
dy=[0,1,0,-1] # 좌 우 위 아래
var_cnt = 0

var_N = int(stdin.readline())
matrix = [list(stdin.readline()) for _ in range(var_N)]
apt=[]

def dfs(x,y):
    global var_cnt
    matrix[x][y] = '0' #방문한 곳은 0으로
    var_cnt += 1
    for i in range(4):
        nx = x + dx[i] #i=0 좌 , i=1 상, i=2 우 , i=3 하
        ny = y + dy[i]
        if nx < 0 or nx >= var_N or ny < 0 or ny >=var_N: # 단지 범위 초과
            continue
        if matrix[nx][ny] == '1': # 인접한 단지 있다면, 
            dfs(nx,ny)

for i in range(var_N):
    for j in range(var_N):
        if matrix[i][j] == '1': # 아파트가 있다면, 
            var_cnt= 0 # 모임 아파트 개수
            dfs(i,j)
            apt.append(var_cnt)

print(len(apt)) # 3
apt.sort() # 7 8 9 
for i in apt:
    print(i)

마무리

바이러스를 풀고 해당 문제를 접하면, dfs 방식으로 재귀함수로 짤 생각을 하는데, 재귀함수 호출 조건을 어떤식으로 설정하는 것이 좋을까에 대한 고민이였다. dx, dy 구조를 접한 순간, 문제를 거침없이 풀 수 있었다.

728x90
반응형