Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- DP
- level3
- dict
- 프로그래머스
- level1
- level0
- 재귀
- 딕셔너리
- 스택
- 코딩테스트
- 백준
- 가상메모리 관리
- 다익스트라
- level2
- 수학
- BOJ
- 구현
- 운영체제
- N과M
- python
- programmers
- BFS
- MYSQL
- dfs
- 그리디
- 힙
- 다이나믹 프로그래밍
- 파이썬
- 가상메모리
- 브루트포스
Archives
- Today
- Total
동캄의 코딩도장
백준 11403 [경로 찾기] 파이썬 본문
https://www.acmicpc.net/problem/11403
#백준 11403 경로 찾기
import sys
input=sys.stdin.readline
N=int(input())
graph=[[]*N for _ in range(N)] #방향 그래프를 저장할 이중 리스트 새성
for i in range(N):
s=list(map(int,input().split())) #각 행에 대해서
for j in range(N):
if s[j]==1: #i,j로 갈 수 있는 지 확인
graph[i].append(j) # 그래프에 추가
answer=[[0]*N for _ in range(N)] #정답을 반환할 이중 리스트 생성
def bfs(start_node):
visited=[0]*(N) #방문했는지 확인하기 위한 리스트
q=[]
q.append(start_node) #시작노드 큐에 추가
while q:
node=q.pop(0) #큐에서 제일 앞 노드를 빼냄
for next_node in graph[node]:
if visited[next_node]==0: #방문 하지 않았다면
visited[next_node]=1 #방문으로 갱신
answer[start_node][next_node]=1 #start_node 에서 next_node로 갈 수 있다고 정답 리스트 값 갱신
q.append(next_node) #큐에 노드 추가
for i in range(N): #각 노드(i)에 대해서 bfs!
bfs(i)
for i in range(N):
for j in range(N):
if j==N-1:
print(answer[i][j])
else:
print(answer[i][j],end=' ')
처음에 문제를 이해하는게 쉽지 않았다. 하지만, 이해하고 나니 bfs문제구나 라는 생각이 바로 들었다!
이 문제의 특이한 점은 보통 bfs 탐색은 visited[start_node]=1로 갱신하지 않는다는 점이다. 즉, 자기 자신에게 못 돌아 올 수도 있는 경우도 고려해야 한다.
'코테 > BOJ' 카테고리의 다른 글
백준 11286 [절댓값 힙] 파이썬 (0) | 2023.03.21 |
---|---|
백준 1074 [Z] 파이썬 (0) | 2023.03.21 |
백준 5525 [IOIOI] 파이썬 (0) | 2023.03.21 |
백준 1992 [쿼드트리] 파이썬 (0) | 2023.03.21 |
백준 1780 [종이의 개수] 파이썬 (0) | 2023.03.20 |