완전 탐색과 시뮬레이션 문제들을 풀면서 느낀점이 있다.
자료구조 완전히 까먹었구나!!
생각해보면 공화국 문제는 애초부터 예시 그림이 힌트였다.
어디서 많이 본 거 같더니..
그래프였다!
그래프? > DFS or BFS? >...라는 방식으로 사고가 되어야 하는데
문제를 읽기만 하고 머리에 담지 않았다.
그냥 자료구조를 까먹은 것이었다!
기본에 충실하기 위해 DFS와 BFS를 다시 공부해보자!
Graph
그래프란, 노드와 간선으로 표현되고 노드를 정점이라고 말한다. 그래프 탐색은 "하나"의 노드를 시작으로 다수의 노드를 "방문"하는 것을 말한다.
그래프는 인접 행렬과 인접 리스트로 표현된다.
인접행렬
2차원 배열로 그래프의 연결 관계를 표현하는 방식이다.
연결되지 않은 노드끼리는 무한의 비용이라고 작성한다.
ex)INF=999999999
인접 리스트
리스트로 그래프의 연결 관계를 표현하는 방식이다.
인접리스트는 '연결리스트'라는 자료구조를 이용해 구현하는데, 파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공한다.
graph = [[] for _ in range(3)]
#노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))
print(graph)
인접 행렬과 인접 리스트의 차이
메모리 측면:
-인접 행렬은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.
-인접 리스트는 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
DFS(Depth-First Search)
깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
(방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다.)
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
def dfs(graph, v, visited):
#현재 노드 방문처리
#방문된 노드 출력
visited[v] = True
print(v, end='')
#현재 노드와 연결된 방문하지 않은 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
#노드가 1번부터 시작하기 때문에 0번째는 비우고 시작한다.
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
#모든 값을 False로 처리하여 방문한 곳이 없다고 default
#index 0번 사용하기 위해 크기를 리스트 크기보다 크게 한다.(실제 index 크기:8/ index 0번 포함시 크기:9)
visited=[False]*9
#정의된 DFS 함수 호출
dfs(graph, 1 visited)BFS(Breadth-First Search)
너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
BFS 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
(방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다.)
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
from collections import deque
def bfs(graph, start, visited):
#큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
#현재 노드 방문 처리
visited[start] = True
#pop으로 큐가 완전히 빌 때까지 반복
while queue:
#큐에서 하나의 원소를 뽑아 출력하기
v = queue.popleft()
print(v, end=' ')
#아직 방문하지 않은 인접 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] =True
#노드가 1번부터 시작하기 때문에 0번째는 비우고 시작한다.
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
#모든 값을 False로 처리하여 방문한 곳이 없다고 default
#index 0번 사용하기 위해 크기를 리스트 크기보다 크게 한다.(실제 index 크기:8/ index 0번 포함시 크기:9)
visited=[False]*9
#정의된 BFS 함수 호출
bfs(graph, 1 visited)DFS는 재귀 호출이 가능하지만 BFS는 탐색 특성상 불가하다.
def dfs(x,y):
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
if graph[x][y] == 0:
graph[x][y] = 1
dfs(x, y+1)
dfs(x, y-1)
dfs(x - 1, y)
dfs(x + 1, y)
return True
return False
#n(행),m(열)값 입력받기
n, m =map(int, input().split())
graph =[]
#빈 그래프 생성 후 n(행)크기의 리스트 만들어 2차원 리스트
for i in range(n):
graph.append(list(map(int, input())))
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j) ==True:
result +=1
print(result)[백준 1260번 BFS와 DFS]
(https://www.acmicpc.net/problem/1260)
#첫번째 노드 v부터 DFS, BFS탐색 시작
def DFS(v):
visited[v]=1
dfs.append(v)
for i in node[v]:
if (visited[i]==0):
DFS(i)
def BFS(v):
visited[v]=1
bfs.append(v)
queue = [v]
while(queue):
for i in node[queue.pop(0)]:
if(visited[i]==0):
visited[i]=1
bfs.append(i)
queue.append(i)
N, M, V = map(int, input().split())
node =[[]for _ in range(N+1)]
visited = [0]*(N+1)
dfs = []
bfs = []
for i in range(M):
a, b = map(int, input().split())
#append를 a,b 지정하지말고 추가하는 방법이 있는지 더 찾아봐야겠다!
node[a].append(b)
node[b].append(a)
for j in range(N+1):
node[j].sort()
DFS(V)
for j in range(N+1):
visited[j]=0
BFS(V)
#DFS, BFS 결과 출력
for m in dfs:
print(m, end=' ')
print()
for n in bfs:
print(n, end=' ')문제 접근방식 :
기존 DFS, BFS 생각하고 그대로 넣었더니 두 개의 리스트를 출력해야하기 때문에 수정해야 했다. for문의 범위를 n+1로 잡지 않아 오류가 났는데 첫 빈 index를 추가하는 것을 잊지 말자!
from collections import deque
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]
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x,y = queue.popleftO()
for i in range(4):
nx = x +dx[i]
ny = y + dy[i]
if nx <0 or ny <0 or nx >=n or ny >= m:
continue
if graph[nx][ny] == 0:
continue
if graph[nx][ny] == 1:
graph[nx][ny] == graph[x][y] + 1
queue.append((nx,ny))
return graph[n-1][m-1]
print(bfs(0,0))