일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- 알고리즘
- django
- 안드로이드
- 코드품앗이
- cos pro 1급
- 개발
- issue
- 안드로이드스튜디오
- AndroidStudio
- android
- 코테
- cos
- Algorithm
- C++
- BAEKJOON
- Flutter
- DART
- 파이썬
- docker
- 동적계획법과최단거리역추적
- 동적계획법
- 백준
- DFS
- 분할정복
- codingtest
- 코딩테스트
- vuejs
- cos pro
- DFS와BFS
- Python
- Today
- Total
Development Artist
[Beakjoon, Python] 2667번 : 단지번호붙이기 본문
도입
백준 단계별 풀기 DFS와 BFS 세 번째 문제이다.
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 구조를 접한 순간, 문제를 거침없이 풀 수 있었다.
'Algorithm > Baekjoon' 카테고리의 다른 글
[Baekjoon, Python] 2178번 : 미로 탐색 (0) | 2021.03.07 |
---|---|
[Baekjoon, Python] 1012번 : 유기농 배추 (0) | 2021.03.06 |
[Baekjoon, Python] 2606번 : 바이러스 (0) | 2021.03.03 |
[Baekjoon, Python] 1260번 : DFS와 BFS (0) | 2021.03.02 |
[Baekjoon, Python] 13305번 : 주유소 (0) | 2021.03.01 |