탐색: DFS와 BFS
데이터 탐색(그래프 탐색) = 원하는 데이터 도달
DFS(Depth-First Search)
; 깊이 우선 탐색은 그래프에서 깊은 부분을 우선으로 탐색
BFS(Breadth-First Search)
; 너비 우선 탐색은 그래피에서 가까운 노드를 우선으로 탐색
DFS:
# DFS 메서드 정의
def dfs(graph, v, visited):
visited[v] = True # 현재 노드를 방문 처리
print('DFS 탐색 순서', [v], v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
print('방문 하지 않은 노드 발견 : ', graph[i])
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출, 시작 노드 1
dfs(graph, 1, visited)-> 파이썬은 스택 구현을 위해 일반적으로 리스트를 활용한다.
실행 결과 :
DFS 탐색 순서 [1] 1 방문 하지 않은 노드 발견 : [1, 7]
DFS 탐색 순서 [2] 2 방문 하지 않은 노드 발견 : [2, 6, 8]
DFS 탐색 순서 [7] 7 방문 하지 않은 노드 발견 : [7]
DFS 탐색 순서 [6] 6 방문 하지 않은 노드 발견 : [1, 7]
DFS 탐색 순서 [8] 8 방문 하지 않은 노드 발견 : [1, 4, 5]
DFS 탐색 순서 [3] 3 방문 하지 않은 노드 발견 : [3, 5]
DFS 탐색 순서 [4] 4 방문 하지 않은 노드 발견 : [3, 4]
DFS 탐색 순서 [5] 5
DFS - 음료수 얼려먹기
문제:N x M 크기의 얼음틀이 있다. 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요.
구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
입력예) 출력 예)
4,5 3
00110
00011
11111
00000
| 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
코드 구현
1. DFS OR BFS (추가 조건이 없다면 DFS)
2.얼음틀 크기 입력 받기
3. 맵 내부 정보 입력받기
4. 상하좌우 값이 0이면 방문
5. 이후 방문한 노드에서 상하좌우 방문
6. 반복하여 모든 지점 방문
7. 방문하지 않은 지점의 수를 카운트
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
# 얼음틀에서 벗어나는 경우에는 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0: # 처음엔 0, 0
# 해당 노드 방문 처리, 얼음 표시
graph[x][y] = 1 # 방문 이후 1, 1
# 상, 좌, 하, 우의 위치 재귀 호출(모든 방향 탐색)
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return True # 방문 끝나면 참 리턴
return False # 재귀 탈출 조건
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result) # 정답 출력BFS:
from collections import deque # deque를 사용
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력하기
v = queue.popleft()
print('BFS 탐색 노드 :', v)
# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
print('새로운 노드 발견 : ', [i], queue)
visited[i] = True
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)실행결과:
BFS 탐색 노드 : 1
새로운 노드 발견 : [2] deque([2])
새로운 노드 발견 : [3] deque([2, 3])
새로운 노드 발견 : [8] deque([2, 3, 8])
BFS 탐색 노드 : 2
새로운 노드 발견 : [7] deque([3, 8, 7])
BFS 탐색 노드 : 3
새로운 노드 발견 : [4] deque([8, 7, 4])
새로운 노드 발견 : [5] deque([8, 7, 4, 5])
BFS 탐색 노드 : 8
BFS 탐색 노드 : 7
새로운 노드 발견 : [6] deque([4, 5, 6])
BFS 탐색 노드 : 4
BFS 탐색 노드 : 5
BFS 탐색 노드 : 6
BFS-미로탈출
문제: 모험가(1, 1)위치 기준으로 N X M 크기 미로에서 괴물을 피해 탈출해야 합니다. 탈출하기 위한 최소 칸의 개수를 구하시오
괴물이 있는 부분은 0, 없는 부분은 1로 표시
최단 거리를 구하는 문제-> 되도록 BFS 사용하자. (속도문제)
입력 예)
5 6
101010
111111
000001
111111
111111
출력 예)
10
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
코드 구현
1. 미로 크키 입력
2. 맵 내부 정보 입력
3. 모든 노드 초기화 (bfs)
4. 초기조건 (0,0) 가정하고
5. 좌표 이탈하면 컨티뉴
6. 상하좌우 방문
7. 최단거리
from collections import deque
def bfs(x,y):
queue=deque() #deque 라이브러리 사용
queue.append((x,y))
while queue: #큐가 빌 때까지 반복
x,y=queue.popleft()
#4가지 방향으로 위치 확인
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
#공간을 벗어나면 무시
if nx<0 or nx>=n or ny<0 or ny>=m:
continue
#벽인 경우==0 무시
if graph[nx][ny]==0:
continue
#1인 경우만 처음 방문하는 경우에만 최단거리 기록
if graph[nx][ny]==1:
graph[nx][ny]=graph[x][y]+1 #거리를 한 칸 증가시킴
queue.append((nx,ny))
#가장 오른쪽 아래까지의 최단거리 반환
return graph[n-1][m-1]
n,m=map(int,input().split())
graph=[]
for i in range(n):
graph.append(list(map(int,input()))) #맵 정보 입력
#네가지 방향
dx=[-1,1,0,0]
dy=[0,0,-1,1]
print(bfs(0,0))문제: 내집은 어디에? 아파트 단지 지도를 입력하여 단지의 개수와 단지별로 집의 개수를 출력하는 프로그램을 작성하시오. (DFS와 BFS 두가지로 구현)
집은 1, 집이 아닌 곳은 0으로 표시함 연결된 아파트는 같은 단지를 의미함.
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 |
코드 구현
1.단지크기 입력받기
2. 단지 정보 입력받기
3.상하좌우 방문
4.DFS-좌표이탈>무시
5.상하좌우 방문
6.집발견하면 갯수 증가
7.집 개수 출력
DFS 구현 코드:
def dfs(x,y,L):
dx=[-1,0,1,0] #4가지 방향 정의
dy=[0,1,0,-1]
for i in range(4): #상하좌우 검사
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n and arr[nx][ny]==1: #새로운 집 발견
arr[nx][ny]=0
cnt_arr[L]+=1 #다음 좌표 설정
dfs(nx,ny,L) #dfs 재귀
n=int(input("단지 크기 입력> "))
arr=[list(map(int,input("단지 지도 세부정보 입력: "))) for i in range(n)]
total_cnt=0
cnt_arr=list()
for i in range(n):
for j in range(n):
if arr[i][j]==1:
arr[i][j]=0
cnt_arr.append(1) # 초기 방문 표시
dfs(i,j,total_cnt) #dfs 탐색 시작
total_cnt+=1
print("총단지수 : ",total_cnt)
cnt_arr.sort()
for i in cnt_arr:
print("각 집의 갯수: ",i)BFS 구현 코드:
from collections import deque
n=int(input("단지 크기 입력: "))
arr=[list(map(int,input("단지 세부 정보 입력:")))for i in range(n)]
cnt=0 #단지 안에 속하는 집의 수
cnt_arr=list() #큐가 ㄱ끝날 때 최종 cnt를 담아줄 배열의 값
dx=[-1,0,1,0]
dy=[0,1,0,-1]
q=deque()
for i in range(n):
for j in range(n):
if arr[i][j]==1:
q.append((i, j)) # 초기 방문 노드 큐에 추가
arr[i][j]=0
cnt=1
while q: # 큐가 존재
x,y=q.popleft() #큐의 현재 노드를 꺼냄
for z in range(4):
nx=x+dx[z]
ny= y+dy[z]
if 0<=nx<n and 0<=ny<n and arr[nx][ny]==1:
arr[nx][ny]=0
cnt+=1
q.append((nx,ny))
cnt_arr.sort()
print("총 단지수 : ",len(cnt_arr))
for i in cnt_arr:
print("각 집의 갯수:",i)
'파이썬 알고리즘' 카테고리의 다른 글
| DFS와 BFS (0) | 2022.07.25 |
|---|---|
| 구현 (0) | 2022.07.21 |
| 그리디 알고리즘 (0) | 2022.07.21 |
| 다이나믹 프로그래밍 (2) | 2022.07.21 |
