DFS/BFS 문제

15. 특정 거리의 도시 찾기

백준에도 같은 문제가 있다. 짠 코드를 채점해보자

www.acmicpc.net/problem/18352

 

import sys
from collections import deque
 
input = sys.stdin.readline
 
# 도시의 개수, 도로의 개수, 최단 거리, 출발 도시의 번호
# 도달 할 수 있는 도시가 없으면 -1
n, m, k, x = map(int, input().split())
visited = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
 
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
 
 
def bfs(start):
    queue = deque()
    queue.append(start)
 
    while queue:
        v = queue.popleft()
 
        for i in graph[v]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = visited[v]+1
    #시작 노드는 0
    visited[x]=0
 
 
bfs(x)
 
check=False
for i in range(len(visited)):
    if visited[i] == k:
        print(i)
        check=True
 
if check==False:
    print(-1)

visited 리스트에 시작노드부터 해당 노드까지의 거리를 담아 출력했다

 

입력 예시	출력 예시
4 4 2 1 1 2  1 3 2 3 2 4	4
4 3 2 1 1 2 1 3 1 4	-1
4 4 1 1 1 2 1 3 2 3 2 4	2 3
4 5 3 1 1 2 1 3 2 3 2 4 4 1	-1 *출발 도시 X에서 출발도시 X로 가는 최단 거리는 항상 0이다

 

 

 

16. 연구소

백준 www.acmicpc.net/problem/14502

 

 

입력 예시	출력 예시
7 7 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0	27
4 6 0 0 0 0 0 0 1 0 0 0 0 2 1 1 1 0 0 2 0 0 0 0 0 2	9
8 8 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	3

 

17. 경쟁적 전염

백준 www.acmicpc.net/problem/18405

import sys
from collections import deque
input = sys.stdin.readline
 
# 시험관 크기, 바이러스 종류
n, k = map(int, input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int, input().split())))
# 초, 위치
s, x, y = map(int, input().split())
# 서 동 남 북
move = [[-1,0],[1,0],[0,-1],[0,1]]
q=[]
for i in range(n):
    for j in range(n):
        if graph[i][j]!=0:
            q.append([graph[i][j], i, j, 0])
q.sort(key=lambda x:x[0])
q=deque(q)
 
def bfs(s):
    while q:
        number, x, y, time = q.popleft()
        if time==s:
            break
 
        for move_x, move_y in move:
            nx=x+move_x
            ny=y+move_y
            if 0<=nx<n and 0<=ny<n and graph[nx][ny]==0:
                q.append([number, nx, ny, time+1])
                graph[nx][ny]=number
    return 0
 
bfs(s)
#결과
print(graph[x-1][y-1])

 

위, 아래로 움직이는 문제면 move 배열을 만들어 동서남북으로 움직이자

 

입력 예시	출력 예시
3 3 1 0 2 0 0 0 3 0 0 2 3 2	3
3 3 1 0 2 0 0 0 3 0 0 1 2 2	0
3 3 1 0 2 0 0 0 3 0 0 0 3 2	0

 

 

 

 

출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)