[백준] 18352 특정 거리의 도시 찾기

[백준] 18352 특정 거리의 도시 찾기

dfs / 파이썬

 

 

[문제]

 

모든 도로의 거리가 1로 동일하므로 bfs를 사용하는 문제임을 알 수 있음

 

 

입력값) n: 도시의 개수 m: 도로의 개수 k: 거리정보 x: 출발 도시의 번호

노드와 간선정보가 인접 행렬방식과 인접 리스트방식중 인접 리스트 방식으로 입력됨을 확인하고 넘어가자

 

 

 

[과정]

1. bfs를 돌리기에 앞서 필요한 배열과 정보들을 저장

    1.1) graph: 인접 리스트 방식으로 해당노드(graph[a])에 연결된 노드와 간선정보를 저장(.append(b,1))

    1.2) visited: 노드의 방문여부를 담은 배열

    1.3) distance: 특정 노드(start)에서 해당 노드까지 가는 거리비용을 담은 배열

 

2. start(시작노드)에서 bfs 실행

    2.1) deque를 선언 후 시작노드를 큐에 저장

    2.2) 해당노드를 방문처리한 후 while문으로 큐를 돌림

    2.3) 큐를 하나 pop한 후 방문여부를 검사하고 방문되지 않은 노드이면 거리비용(distance)를 갱신 후 큐에 해당 노드를 넣어주고 방문처리

 

3. 최단거리가 k인 도시의 번호를 오름차순으로 출력

    3.1) 조건에 맞는 도시가 존재하지 않을경우 -1 출력

 

 

 

 

[소스코드]

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

def bfs(graph, start, visited):
    queue = deque()
    queue.append(start)
    visited[start] = True

    while queue:
        node = queue.popleft()
        for now, dist in graph[node]:
            if not visited[now]:
                distance[now] = distance[node]+dist
                queue.append(now)
                visited[now] = True   
    return graph

# 그래프의 기본정보 저장 
n,m,k,x = map(int, input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    a,b = map(int, input().split())
    # 노드, 간선
    graph[a].append((b,1))
    
visited = [False] * (n+1)
distance = [0] * (n+1)

bfs(graph, x, visited)

# 최단거리가 k인 도시의 번호 출력 
answer = []
for idx, dist in enumerate(distance):
    if dist == k:
        answer.append(idx)
if not answer:
    print(-1)
else:
    answer.sort()
    for ans in answer:
        print(ans)

 

 

---

[통과]

 

 

초반 2개는 bfs만 돌리고 3번작업을 안해주고 바로 제출해서 틀림

 

이후 5개는 출력부분이 틀렸나 계속해보다가 distance배열과 visited배열의 초기상태를 도시의 개수(n)만큼 해야하는데 간선의 개수(m)만큼 돌려서 인덱스 에러가 남

 

마지막에 해당 부분만 m->n으로 고치고 통과! (한참찾았네ㅎㅎ..)