BFS / DFS 문제풀기 Q15 - Q22

동빈나 알고리즘 유형별 기출문제 1. 그리디 2. 구현 3. DFS/BFS 4. 정렬 5. 이진 탐색 6. 다이나믹 프로그래밍 7. 최단 경로 8. 그래프 이론 9. 2020년 상반기 삼전 기출 문제

 

Q15 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

 

 

몰랐던 점 

1. 도대체 단방향 도로 정보를 어떤 식으로 입력을 받아야 할까.

먼저 빈 graph 2차원 배열을 만들고

그 안에 a 도시에 연결된 b 도시들을 나열하도록 append 하면 되었다.

 

2. 최단 거리를 어떤 식으로 누적해서 저장해야 할까

최단 거리 값을 방문하지 않았다면 -1로 쭉 셋팅해놓고

각 도시 인덱스 값에 distance 값을 누적해서 더하는 방식으로 구현하였다.

방문하지 않은 도시라면 다음 노드에 현재 노드 + 1 값을 넣고 

큐에 next_node를 append하였다. 

 

따라서 bfs는 각 경로까지 갈 때 거쳐간 거리를 계산할 때 쓴다. 

즉, 출발 - 도착점까지 최단 경로를 찾을 때 쓴다. 

# 15. 특정 거리의 도시 찾기
from collections import deque

# 도시 개수, 도로 개수, 거리 정보, 출발 도시 입력
n, m, k, x = map(int, input().split())
# 2차원으로 그래프 정보 담기
# graph = [list(map(int, input().split())) for _ in range(n + 1 )]
# 각 노드 행에 단방향 도로를 추가하는 2차원 리스트 만들기
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)


# BFS 만들기
def bfs(x, k):
    # 모든 도시에 대한 최단 거리 초기화
    distance = [-1] * (n + 1)
    distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정
    # 큐 구현을 위해 deque 사용
    queue = deque()
    # 첫번째 시작 도시를 넣는다.
    queue.append(x)
    # 큐가 빌 때까지 반복한다.
    while queue:
        # 시작 도시에서 각 도시까지의 최단거리를 구한다.
        now_node = queue.popleft()
        for next_node in graph[now_node]:
            # 아직 방문하지 않은 도시라면
            if distance[next_node] == -1:
                distance[next_node] = distance[now_node] + 1
                queue.append(next_node)
    city = []
    # 최단 거리가 k인 도시를 city 라는 리스트에 추가한다.
    for i in range(1, n + 1):
        # print(i, ": ", distance[i]," ")
        if distance[i] == k:
            city.append(i)
    # 만약 도시 명단이 없다면 -1을 반환한다.
    if not city:
        print("-1")
        return
    # 최단 거리로 이동한 도시 명단을 sort로 정렬한다.
    city.sort(reverse=False)
    for i in range(len(city)):
        print(city[i])
    return

# 도시 번호 출력
bfs(x, k)

 

Q16 연구소

https://www.acmicpc.net/problem/14502

 

1. 빈 공간에 임의로 3개의 벽을 세우는 코드는 어떻게 구현해야 할까

count를 +=1해서 3까지 늘려주면서 dfs(count)로 재귀함수를 써준다. 

# 빈 공간에 울타리 설치
for i in range(n):
    for j in range(m):
        if data[i][j] == 0:
            data[i][j] = 1
            count += 1
            dfs(count)
            data[i][j] = 0
            count -= 1

에서 재귀함수 부분이 이해가 안된다.

dfs(count)하고 나서 뒤에 코드는 언제 실행되는 거야 도대체..