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
- 가상메모리 관리
- BFS
- 재귀
- BOJ
- 수학
- 브루트포스
- N과M
- 가상메모리
- 다익스트라
- programmers
- 백준
- 딕셔너리
- DP
- 프로그래머스
- 힙
- 다이나믹 프로그래밍
- 그리디
- 운영체제
- python
- dfs
- level0
- 스택
- MYSQL
- 코딩테스트
- level2
- level3
- 구현
- level1
- dict
- 파이썬
Archives
- Today
- Total
동캄의 코딩도장
백준 2178 [미로 탐색] 파이썬 본문
https://www.acmicpc.net/problem/2178
#백준 2178 미로 탐색
import sys
input=sys.stdin.readline
dr=[1,0,-1,0] #위 아래
dc=[0,-1,0,1] # 좌 우
N,M=map(int,input().split())
maze=[]
for _ in range(N):
maze.append(list(map(int,input().rstrip()))) # 미로 값 저장
def bfs(start,maze):
visited=[[0]*M for _ in range(N)] #방문 값을 0으로 초기화
start_r,start_c=start #시작 행,렬 받음
visited[start_r][start_c]=1 # 시작 행 렬을 1로 초기화
q=[]
q.append([start_r,start_c]) #큐에 추가
while q:
r,c=q.pop(0) #큐에서 뺌
if r==N-1 and c==M-1: #도착하면
return visited[r][c] #최종 거리를 리턴
for i in range(4): #상하좌우로 탐색
R=r+dr[i]
C=c+dc[i]
if 0<=R<N and 0<=C<M and maze[R][C]==1 and visited[R][C]==0: #미로 안에 있는지 탐색 & 갈 수 있는 길인지 & 방문했는지 탐색
visited[R][C]=visited[r][c]+1 #거리를 갱신 (visted 이용)
q.append([R,C]) #큐에 추가
# for val in visited:
# print(val)
# print()
ans=bfs([0,0],maze)
print(ans)
bfs를 이용해서 해결하려고 하는데, 도저히 안풀렸다.
큐에서 값을 빼낼 때 pop()을 계속 사용했던 것이다.
pop() 과 pop(0)은 엄연히 다른데 말이다...
'코테 > BOJ' 카테고리의 다른 글
백준 2630 [색종이 만들기] 파이썬 (0) | 2023.03.20 |
---|---|
백준 1389 [케빈 베이컨의 6단계 법칙] 파이썬 (0) | 2023.03.20 |
백준 18870 [좌표 압축] 파이썬 (0) | 2023.03.20 |
백준 11659 구간 합 구하기 (0) | 2023.03.20 |
백준 1764 [듣보잡] 파이썬 (0) | 2023.03.20 |