탐색
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- DFS/BFS
자료구조
- 데이터를 표현하고 관리하고 처리하기 위한 구조
- 스택 : FILO , 파이썬 리스트 그대로 사용
- 큐 : FIFO , collections 모듈에서 제공하는 deque 자료구조(데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적), deque.popleft()
- 오버플로 : 삽입 시 저장 공간을 벗어나 데이터가 넘침
- 언더플로 : 데이터가 없는 상태에서 삭제 연산 시
그래프
- 노드(node), 간선(edge), 정점(vertex)
- 표현방식
- 노드 0에서 노드1까지 거리 7, 노드2까지 거리5
- 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 [[0,7,5], [7,0,INF], [5,INF,0]] 연결 관계 확인 속도 빠름
- 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 [[(1,7),(2,5)], [(0,7)], [(0,5)]] 노드개수 많을 수록 메모리 효율
DFS
- Depth-Fisrt Search, 깊이 우선 탐색, 깊이 있는 노드부터 탐색
- 스택 자료구조 활용
- 동작과정
- 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 삽입하고 방문처리
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 3. 1,2과정을 수행할 수 없을 때까지 반복
재귀적으로 구현
def dfs(graph,start,visited):
if visited[start] == False:
visited[start] = True
print(start)
for i in graph[start]:
dfs(graph,i,visited)
elif visited[start] == True:
return
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
dfs(graph,1,visited)책에서는 방문했는지 체크하고 dfs를 수행하는데 나는 일단 수행시키고 그 위치가 방문되었는지 아닌지 체크한다.
책에서 한대로하면 재귀 덜되고 조건문도 필요없을 듯
반복적으로 구현
def dfs(graph,start,visited):
stk = [start]
visited[start] = True
print(start)
while stk:
now = stk[-1]
found = False
for i in graph[now]:
if visited[i] == False:
stk.append(i)
visited[i] = True
print(i)
found = True
break
if found == False:
stk.pop()
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
dfs(graph,1,visited)스택의 특성으로 구현 가능
BFS
- Breadth First Search, 너비 우선 탐색, 가까이 있는 노드부터 탐색
- DFS보다 일반적으로 빠른 편
- 동작 방식
- 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 3. 2번을 더 이상 수행할 수 없을 때 까지 반복한다.
반복적으로 구현
from collections import deque
def dfs(graph,start,visited):
que = deque()
que.append(start)
visited[start] = True
while que:
now = que.popleft()
print(now)
for i in graph[now]:
if visited[i] == False:
que.append(i)
visited[i] = True
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False]*9
dfs(graph,1,visited)
큐에서 pop 된 순서가 탐색 순서다.
꿀팁
- 2차원 배열에서 탐색 문제를 만나면 그래프 형태로 바꿔 생각하면 더 쉬울 것
문제1. 음료수 얼려 먹기
1차 시도
#음료수 얼려 먹기 18:42 시작
from collections import deque
N,M = list(map(int,input().split()))
box = []
for i in range(0,N):
box.append(list(map(int,input()))) #box[N-1][M-1]
visited = [[False]*M] * N
#모든 칸에 대해 검사
#지금 칸이 뚫려있고 방문이 안됨
#BFS 로 다 채우고
#아이스크림 개수 += 1
##지금 칸이 뚫려있고 방문됨 은 있을 수가 없네
##지금 칸이 막혀있음 다음 루프가즈아
#위 왼 밑 오
dx = [0,-1,0,1]
dy = [-1, 0, 1, 0]
res = 0
for i in range(0,N):
for j in range(0,M):
if box[i][j] == 0 and visited[i][j] == False:
que = deque()
que.append((i,j)) #(N,M) (y,x) (i,j)
box[i][j] = 1
visited[i][j] = True
res += 1
while que:
print(que)
y,x = que.popleft()
for k in range(0,4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or ny < 0 or nx >= M or ny >= N:
pass
elif box[ny][nx] == 0 and visited[ny][nx] == False:
que.append((ny,nx))
print(que)
box[ny][nx] = 1
print(res)왜 visited가 모두 true로 되는지 고민중. 그거 땜에 box도 다 안채워지는 듯.
대충 구상, 구현은 30분정도 걸린 것 같은데 1시간째 계속 막힘.
문제 해결
#음료수 얼려 먹기 18:42 시작
from collections import deque
N,M = list(map(int,input().split()))
box = []
for i in range(0,N):
box.append(list(map(int,input()))) #box[N-1][M-1]
#모든 칸에 대해 검사
#지금 칸이 뚫려있고 방문이 안됨
#BFS 로 다 채우고
#아이스크림 개수 += 1
##지금 칸이 뚫려있고 방문됨 은 있을 수가 없네
##지금 칸이 막혀있음 다음 루프가즈아
#위 왼 밑 오
dx = [0,-1,0,1]
dy = [-1, 0, 1, 0]
res = 0
for i in range(0,N):
for j in range(0,M):
if box[i][j] == 0:
que = deque()
que.append((i,j)) #(N,M) (y,x) (i,j)
box[i][j] = 1
res += 1
while que:
y,x = que.popleft()
for k in range(0,4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or ny < 0 or nx >= M or ny >= N:
pass
elif box[ny][nx] == 0:
que.append((ny,nx))
box[ny][nx] = 1
print(res)풀다가 생각해보니 어차피 박스는 1로 바뀌면 방문한거랑 마찬가지라 방문조건 체크는 필요없었는데 그냥 넣은 김에 넣은 채로 풀려했었다.
근데 방문조건 체크에서 계속 발목잡혀서 그냥 빼버렸더니 완벽하게 동작.
box[][] == 0 이랑 visited[][] == False 처럼 계속 같이 놀게 해줬는데 왜 visited에 문제가 있었던 건지는 아직 모르겠음.
test case
4 5
00110
00011
11111
00000
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111
꿀팁
배열 크기 변수랑 내가 생각한 x, y 좌표를 혼동하지 않도록 합쳐서 주석으로 표현해놓자
#(N,M) (y,x) (i,j)
문제2. 미로 탈출
from collections import deque
N,M = list(map(int,input().split())) # N,M Y,X
world = []
for i in range(0,N):
world.append(list(map(int,input())))
res = 0
start = (0,0) #문제에선 1,1
#시작점 큐에 넣고 방문체크
#큐에 있는동안
#큐에서 popleft
#그 위치에서 4방향 검사
#1이면 큐에 넣고 방문 체크
dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
que.append(start)
world[0][0] = 2 #0은 괴물 1은 길 2는 방문한곳
visited = []
for i in range(N):
visited.append([])
for j in range(M):
visited[i].append(1)
while que:
for i in world:
print(i)
print('---')
for i in visited:
print(i)
print('---')
y,x = que.popleft()
for k in range(0,4):
ny = y + dy[k]
nx = x + dx[k]
if ny < 0 or nx < 0 or ny >= N or nx >= M:
continue
if world[ny][nx] == 1:
que.append((ny,nx))
world[ny][nx] = 2
visited[ny][nx] = visited[y][x] + 1
a = [[1]*9]*9 이런 식으로 리스트를 초기화하니까 메모리가 참조된 채로 복사되는 것이 문제였음.
곱하기로 선언하지말 것.
위에 visited 문제도 이거때문인 듯