1260 DFS와 BFS, 1697 숨바꼭질, 2606 바이러스

1260 DFS와 BFS, 1697 숨바꼭질, 2606 바이러스

 

1260 DFS와 BFS

from collections import deque

def dfs(v):
	print(v, end=' ')
	visited[v] = True
	for e in adj[v]:
		if visited[e] == False:
			dfs(e)
			
def bfs(v):
	q = deque([v])
	while q:
		v = q.popleft()
		if visited[v] == False:
			visited[v] = True
			print(v, end=' ')
			for e in adj[v]:
				if visited[e] == False:
					q.append(e)
					
n, m, v = map(int, input().split())
adj = [[] for _ in range(n+1)]

for _ in range(m):
	x, y = map(int, input().split())
	adj[x].append(y)
	adj[y].append(x)
	
for e in adj:
	e.sort()
	
visited = [False] * (n+1)
dfs(v)
print()
visited = [False] * (n+1)
bfs(v)

- dfs, bfs 반복해서 익히기

 

 

1697 숨바꼭질

from collections import deque

MAX = 100001
n, k = map(int, input().split())
array = [0] * MAX

def bfs():
	q = deque([n])
	while q:
		now_pos = q.popleft()
		if now_pos == k:
			return array[now_pos]
		for next_pos in (now_pos - 1, now_pos + 1, now_pos *2):
			if 0 <= next_pos < MAX and not array[next_pos]:
				array[next_pos] = array[now_pos] + 1
				q.append(next_pos)
				
print(bfs())

- bfs로 풀면 된다는데 아이디어가 잘 생각나지 않았다. 아직 개념이 안세워진 듯

 

2606 바이러스

n = int(input())
k = int(input())
array = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(k):
	x, y = map(int, input().split())
	array[x].append(y)
	array[y].append(x)

count = -1	

def bfs(v):
	global count
	count += 1
	visited[v] = True
	for e in array[v]:
		if visited[e] == False:
			bfs(e)
			
bfs(1)
print(count)

- dfs를 이용해서 풀이함

- 함수 내에 밖에서 선언한 변수 사용 시 'global 변수명' 이용