Search

특정 거리의 도시 찾기

문제 : 특정 거리의 도시 찾기

풀이

해결에 필요한 핵심 아이디어: BFS(너비 우선 탐색)

해결 시나리오

벽을 세울 수 있는 모든 조합에 대해 BFS (너비 우선 탐색)를 수행
시작점 x에 넣고 탐색 시작
큐에서 원소들을 하나씩 꺼내고, 인접 리스트로 구현한 graph에서 해당 노드와 연결된 노드(간선 정보) 확인
아직 확인하지 않은 간선 정보(INF)라면 직전 큐에서 꺼낸 노드값 + 1 로 값을 갱신
값이 갱신된 간선 정보를 큐에 삽입
위의 과정을 큐가 빌 때까지 반복 수행
업데이트된 그래프의 값 중 k와 일치하는 값을 가진 도시 번호를 오름차순으로 출력

시간 복잡도

인접 리스트로 구현한 그래프의 경우,
시간 복잡도는 O(N + M) ( N: 노드 개수, M: 간선 개수)
N, M은 각각 최대 300,000, 1,000,000이므로 N + M의 최대값은 1,300,000
→ 시간 제한(2초) 무난히 통과
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.