def factorial_recursion(n):
if n<=1:
return 1
return n*factorial_recursion(n-1)
예1)
def dfs(graph, v, visited):
# 현재 노드를 방문처리
visited[v]=True
print(v,end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
# 각 노드가 연결된 정보를 표현(0번 인덱스는 무시)
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)
# 1 2 7 6 8 3 4 5
예2) 음료수 채우기
def dfs(x,y):
# 주어진 범위를 벗어나면 즉시 종료
if x<=-1 or x>=n or y<=-1 or y>=m-1:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y]==0:
# 해당 노드 방문 처리
graph[x][y]=1
# 해당 노드 상,하,좌,우 모두 재귀적으로 호출
dfs(x-1,y)
dfs(x,y-1)
dfs(x+1,y)
dfs(x,y+1)
return True
return False
n,m=map(int, input().split())
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)
예1)
from collections import deque
def bfs(graph, start, visited):
# 시작 값으로 큐 초기화
queue=deque([start])
# 시작 노드 방문 처리
visited[start]=True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v=queue.popleft()
print(v, end=' ')
# 방문하지 않은 인접 노드들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
# 각 노드가 연결된 정보를 표현(0번 인덱스는 무시)
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문한 정보를 표현
bfs(graph, 1, visited)
# 1 2 3 8 7 4 5 6
예2) 미로 탈출
from collections import deque
def bfs(x,y):
# bfs이므로 큐 사용
queue=deque()
queue.append((x,y))
# 큐가 빌 때까지 반복
while queue:
x,y=queue.popleft()
# 현재 위치에서 상,하,좌,우 확인
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
# 괴물이 있는 경우 무시
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))
예3) 특정 거리의 도시 찾기
from collections import deque
n,m,k,x=map(int,input().split())
# 도로 정보 입력 받기 위한 리스트. 인덱스가 도시 번호, 각 원소가 연결된 도시들
graph=[[] for _ in range(n+1)]
# 연결된 도시들 도로 정보
for _ in range(m):
a,b=map(int,input().split())
graph[a].append(b)
# 모든 도시에 대한 최단거리 초기화
distance=[-1]*(n+1)
# 출발 도시까지의 거리는 0
distance[x]=0
q=deque([x])
while q:
now=q.popleft()
# graph[now]는 현재 도시에서 갈 수 있는 모든 도시
for next_node in graph[now]:
# 각 도시를 확인해서 아직 방문하지 않은 도시라면
if distance[next_node]==-1:
# 최단거리를 갱신
distance[next_node]=distance[now]+1
q.append(next_node)
# 최단거리가 k인 모든 도시의 번호를 오름차순 출력
check=False
for i in range(1,n+1):
if distance[i]==k:
print(i)
check=True
# 최단거리가 k인 도시가 없다면 -1 출력
if check==False:
print(-1)
예4) 바이러스 증식
from collections import deque
n,k=map(int,input().split())
graph=[] # 전체 보드 정보
data=[] # 바이러스에 대한 튜플 형태 정보
for i in range(n):
# 보드 정보를 한 줄 단위로 입력하고
graph.append(list(map(int,input().split())))
#한 줄마다 정보 추출
for j in range(n):
# 해당 위치에 바이러스가 존재하는 경우
if graph[i][j]!=0:
# (바이러스 종류, 시간, 위치x, 위치y) 삽입
data.append((graph[i][j], 0, i, j))
# 정렬 이후에 큐로 옮기기(낮은 번호의 바이러스가 먼저 증식하므로)
data.sort()
q=deque(data)
target_s, target_x, target_y=map(int, input().split())
# 바이러스가 퍼져나갈 수 있는 4가지 위치
dx=[-1,0,1,0]
dy=[0,1,0,-1]
while q:
virus, s, x, y=q.popleft()
# 5초가 지나거나 큐가 빌 때까지 반복
if s==target_s:
break
# 현재 위치에서 주변 4가지 위치를 각각 확인
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
# 현재 위치로 이동할 수 있는 경우
if 0<=nx and nx<n and 0<=ny and ny<n:
# 아직 방문하지 않았다면 그 위치에 바이러스 넣고 시간+1
if graph[nx][ny]==0:
graph[nx][ny]=virus
q.append((virus, s+1, nx, ny))
print(graph[target_x-1][target_y-1])