일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 템플릿 문자열
- 회원가입 폼
- 정글sw
- malloc-lab
- React
- 회원가입
- 사용자 정의 객체
- 리액트
- 백준
- conding test
- HTML
- sw정글사관학교
- 프로그래머스
- 목록 창 만들기
- SW정글
- JavaScrpit
- Coding Test
- dfsbfs
- sw 정글
- 코딩테스트
- onChange
- PINTOS
- python
- Spring
- javascript
- Express
- 자바스크립트 문자열 변수
- html input
- 자바스크립트
- node.js
Archives
- Today
- Total
코드치고 무게치고
[백준 python] 18352번 특정 거리의 도시 찾기- DFS/BFS 본문
[백준 python] 18352번 특정 거리의 도시 찾기- DFS/BFS
레벨: 실버 2
언어: python
📑풀이 과정
이 문제에서 보면 모든 도로의 거리는 '1'
이란 조건이 있다.
그래프에서 모든 간선(문제에서 도로)의 길이가 동일 할 때는 BFS를 이용하여 최단 거리를 찾을 수 있다.
일반적으로 DFS/BFS 알고리즘을 배울때 방문여부를 저장하는 배열을 사용하는데
이 문제에서는 방문여부를 저장하는 배열에 거리 정보를 담아서 탐색하면된다.
distance
라는 거리 정보를 답은 배열을 -1로 초기화 한다.
탐색시 -1의 값은 아직 방문하지 않은 노드(도시)이다.
그리고 문제 설명에서 출발 도시 X에서 X로 가는 최단거리는 항상 0이니distance[x] = 0
으로 초기화 해준다.
그 후 탐색을 하면서 방문하지 않은 다음 도시(next)에 현재 탐색중인(now)의 거리 +1을 넣어 준다.
그리고 distance
를 조사하여 k와 같은 값이면 출력 k와 같은 값이 하나도 없다면 -1을 출력한다.
📋풀이 코드
import sys
from collections import deque
input = sys.stdin.readline
# N 도시 수, M 도로 수, K 거리 정보 X 출발 도시
N, M, K, X = map(int, input().split(' '))
graph = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, input().split(' '))
graph[a].append(b)
distance = [-1] *(N+1)
distance[X] = 0
# BFS 부분
q = deque([X])
while q:
now = q.popleft()
for next in graph[now]:
if distance[next] == -1:
distance[next] = distance[now]+1
q.append(next)
# K값이 distance에 있다면 i값출력 없다면 -1 출력
if K in distance:
for i in range(1, N+1):
if distance[i] == K:
print(i)
check = True
else:
print(-1)
'개발공부 > 코딩테스트 준비' 카테고리의 다른 글
[백준 python] 18428번 감시 피하기 (0) | 2022.03.15 |
---|---|
[백준 python] 18405번 경쟁적 전염 - DFS/BFS (0) | 2022.03.12 |
[백준 python] 12904번 A와 B 그리디 (0) | 2022.03.11 |
[백준 python] 1339번 단어 수학 - 그리디 (0) | 2022.03.10 |
[백준 python] 19941번 햄버거 분배 - 그리디 (0) | 2022.03.10 |
Comments