1. dfs
1) 인접행렬이 주어진 경우
N, M = map(int, input().split())
AjMat = [[0] * (N + 1) for _ in range(N+1)]
visited = [0 for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
AjMat[a][b] = AjMat[b][a] = 1
def dfs(i):
visited[i] = 1
for k in range(1, N + 1):
if AjMat[i][k] == 1 and visited[k] == 0:
dfs(k)- 아래 2)의 경우 메모리 초과가 발생하는 경우가 있어서 1)을 디폴트로 사용할 예정.
2) ditctionary로 주어진 경우
def dfs_recursive(graph, start, visited = []):
visited.append(start)
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited- visited를 매개변수에서 디폴트값을 설정할 때 재귀호출되는 모든 함수들이 visited를 공유하게 된다. 신기한데 왜 그런진 아직 모르겠다. 꼭 이 조건이어야만 하는건지도 모르겠다.
- 출처 : https://data-marketing-bk.tistory.com/44
cycle
-
관련 문제 : 백준 10265 MT
위 문제를 풀면 아래의 것들을 한 번에 구할 수 있다. 즉 웬만한 cycle를 dfs로 다루는 테크닉을 구사할 수 있게 된다. 많이 복습하자.- cycle의 구성 원소 하나로 cycle 마킹하기
- cycle의 길이 구하기
- cycle에서 곁가지까지 포함한 연결요소의 길이 구하기
-
cycle를 dfs로 구현하는데 가장 필요한 것은
visited list이외에finished list를 관리하는 것이다. 아래 그림을 보면 이해하는데 도움이 될 것이다.
출처 : https://blog.naver.com/kks227/220785731077 -
위의 빨간색 글씨 부분, 즉 next는 방문했지만, 아직 탐색이 마쳐지지 않은 노드라면 현재 curr를 가칭 head of cycle로 삼고 cycle을 돌며 cycle에 속하는 노드들을 추가한다. 그전까지는 계속해서 재귀호출을 통해 깊이 우선 탐색을 실행한다.
-
dfs는 기본이 FILO의 스택을 사용하는 것. 재귀호출로 dfs를 구현하는 것 또한 마찬가지여서 프로세스 스택에 차례 차례 함수를 쌓아올리며 마지막 호출된 함수부터 리턴된다. 이러한 점을 고려했을 때 함수가 실행되는 첫부분에
visit[curr] = True문장을 적어주며, 리턴 직전에finished[curr] = True로 적어준다. 이를 통해 재귀 호출로 함수가 쌓아 올려지면서visit을 체크하며, 함수가 리턴되면서fisniehd를 체크하게 된다.
cycle에서 곁가지 개수 구하기
- 관련 문제 : 백준 9466 텀 프로젝트
그리디로 간단하게 풀 수 있다.
import sys
input = sys.stdin.readline
def solve():
n = int(input())
prefer = [0] + list(map(int, input().split()))
visited = [0] + [False] * n
answer = 0
for i in range(1, n+1):
if visited[i]:
continue
now = i
while not visited[now]:
visited[now] = True
now = prefer[now]
other = i
while other != now:
answer += 1
other = prefer[other]
return answer
for _ in range(int(input())):
print(solve())
2. bfs
원래 사용하던 방법은 deque.leftpop()을 이용한 Queue와 visit 리스트를 따로 관리하는 것이었으나,
-
리스트를 for문으로 순회하는 방법으로 Queue를 흉내낼 수 있다. 이렇게 하면
for _ in range(len(dequq))문을 사용하지 않고 bfs의 level을 관리할 수 있다. -
주어진 맵에 따른 기호를 저장함으로써
visit관리를 따로 안해도 된다. 시간복잡도, 공간복잡도 두 측면에서 모두 우월하다. -
관련 문제 : 백준 2206 벽 부수고 이동하기
import sys
def bfs():
N, M = map(int, input().split())
field = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
q = [(0, 0, False)]
min_len = 1
while q:
nq = []
for r, c, hammer_used in q:
if r == N - 1 and c == M - 1:
return min_len
for nr, nc in [(r, c + 1), (r + 1, c), (r, c -1), (r - 1, c)]:
if -1 < nr < N and -1 < nc < M:
if hammer_used:
if field[nr][nc] == '0':
field[nr][nc] = '2'
nq.append((nr, nc, hammer_used))
else:
if field[nr][nc] == '1':
nq.append((nr, nc, True))
elif field[nr][nc] in {'0', '2'}:
nq.append((nr, nc, hammer_used))
field[nr][nc] = '3'
q = nq
min_len += 1
return -1
print(bfs())