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 | 31 |
Tags
- 너비우선탐색
- 삼성빈출
- 20006
- 그래프
- 그리디
- 삼성코테기출
- Python
- BFS
- 수학
- 20922
- 구현
- 토스유튜브
- 그리디알고리즘
- 28215
- 3dgs
- 시뮬레이션
- 코테
- 토스독학
- 백준
- 토스만능문장
- mcp란
- mcp튜토리얼
- 최단거리추적
- mcp사용법
- 미지의 공간탈출
- 토익스피킹
- DP
- 그래프탐색
- 토스
- 시계토끼제니쌤
Archives
- Today
- Total
Victory in my life
Baekjoon 2178 | 미로 탐색(Python) 본문
📌문제
SILVER1 / bfs / 그래프 탐색 / 그래프
https://www.acmicpc.net/problem/2178
📌문제 분석 및 설계
문제를 봤을 때, [ 최소의 칸 수 / 입력 처리 ]가 핵심이라고 생각했다.
완전히 기본중에 기본 bfs문제라, bfs 처음 연습할 때 좋은 문제다.
따라서 아래와 같은 요소들로 설계를 했다.
1. bfs로 탐색하면서 이전 위치를 기록하고, 탐색을 마친 후 N,M부터 역으로 1,1까지 가면서 경로추적하며 최소 칸 수 계산
2. grid를 줄 때, 입력을 붙여서 주기때문에 따로 처리
생각해보니 경로추적이 불필요하다고 생각해 최단거리 추적하는 방식으로 변경했다.
두 버전 모드 코드를 업로드했다.
📌소스 코드
#경로 추적 버전
from collections import deque
dxs,dys=[-1,0,1,0],[0,1,0,-1]
n,m=map(int,input().split())
grid=[[0]*m for _ in range(n)]
for i in range(n):
for j,k in enumerate(input()):
grid[i][j]=int(k)
def can_go(x,y):
return 0<=x<n and 0<=y<m and grid[x][y]==1
path=[[0]*m for _ in range(n)]
def bfs():
q=deque([(0,0)])
path[0][0]=1
while q: #deque는 비어있을 때 False로 평가
x,y=q.popleft()
for dx,dy in zip(dxs,dys):
nx,ny=x+dx,y+dy
if can_go(nx,ny) and path[nx][ny]==0:
if (nx,ny)==(n-1,m-1):
path[nx][ny]=(x,y)
return
else:
q.append((nx,ny))
path[nx][ny]=(x,y)
bfs()
x,y=n-1,m-1
cnt=1
while (x,y)!=(0,0):
x,y=visited[x][y]
cnt+=1
print(cnt)
#최단거리 추적 버전
from collections import deque
dxs,dys=[-1,0,1,0],[0,1,0,-1]
n,m=map(int,input().split())
grid=[[0]*m for _ in range(n)]
for i in range(n):
for j,k in enumerate(input()):
grid[i][j]=int(k)
def can_go(x,y):
return 0<=x<n and 0<=y<m and grid[x][y]==1
distance=[[0]*m for _ in range(n)]
def bfs():
q=deque([(0,0)])
distance[0][0]=1
while q: #deque는 비어있을 때 False로 평가
x,y=q.popleft()
for dx,dy in zip(dxs,dys):
nx,ny=x+dx,y+dy
if can_go(nx,ny) and distance[nx][ny]==0:
q.append((nx,ny))
distance[nx][ny]=distance[x][y] + 1
return distance[n-1][m-1] # 도착 지점의 최단 거리 반환
print(bfs())
'CodingTest > Baekjoon' 카테고리의 다른 글
Baekjoon 1343 | 폴리오미노 (Python) (0) | 2025.02.26 |
---|---|
Baekjoon 14940 | 쉬운 최단거리 (Python) (0) | 2025.02.26 |
Baekjoon 1138 | 한 줄로 서기(Python) (0) | 2025.02.25 |
Baekjoon 20006 | 랭킹전 대기열(Python) (0) | 2025.02.24 |
Baekjoon 1913 | 달팽이(Python) (0) | 2025.02.21 |