일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- BFS
- 가상메모리
- MYSQL
- 백준
- 코딩테스트
- level3
- N과M
- 그리디
- 다익스트라
- level2
- level1
- dfs
- programmers
- 수학
- BOJ
- 다이나믹 프로그래밍
- 브루트포스
- 재귀
- 가상메모리 관리
- 구현
- 딕셔너리
- python
- level0
- 운영체제
- 스택
- DP
- dict
- 힙
- 프로그래머스
- 파이썬
- Today
- Total
동캄의 코딩도장
백준 2206 [벽 부수고 이동하기] 파이썬 본문
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
# 백준 2206 벽 부수고 이동하기
from collections import deque
import sys
input = sys.stdin.readline
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
N, M = map(int, input().split())
field = []
wall = deque([])
for i in range(N):
s = list(map(int, input().rstrip()))
for j in range(M):
if s[j] == 1:
wall.append([i, j])
field.append(list(map(int, s)))
def bfs(r, c):
q = deque([])
q.append([r, c])
while q:
r, c = q.popleft()
for i in range(4):
r_ = r+dr[i]
c_ = c+dc[i]
if 0 <= r_ < N and 0 <= c_ < M and field_[r_][c_] == 0:
field_[r_][c_] = field_[r][c]+1
q.append([r_, c_])
answer = 10000
for w in wall:
field_ = []
i, j = w
for k in range(N):
field_.append(list(map(int, field[k])))
field_[i][j] = 0
bfs(0, 0)
if field_[N-1][M-1] != 0:
answer = min(answer, field_[N-1][M-1])
if answer == 10000:
print(-1)
else:
print(answer+1)
브루트포스를 통해 모든 장애물을 하나씩 0으로 만들고, bfs를 실행하는 방식으로 문제를 해결하려고하였다.
하지만, 모든 장애물을 하나씩 0으로 만들고 bfs를 실행하는 방식은.. 정말 비효율적이다...(시간초과 발생)
bfs를 한번만 실행하되, 장애물을 한 번 부쉈다는 징표를 주면 어떨까? 라는 생각을 하였다.
생각을 하던 도중... 장애물을 안 부순 visit 거리값과 한 번 부순 visit 거리 값 중 어떤 것으로 다음 visit값을 갱신해야할지 미궁으로 빠졌다... ( 다음에 벽을 부술지 안부술지 모르기 때문)
결국에는 다른 분의 풀이를 보고 이해하였다.
https://pacific-ocean.tistory.com/348
[백준] 2206번(python 파이썬)
문제 링크: https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당
pacific-ocean.tistory.com
이 분의 풀이이다.
# 백준 2206 벽 부수고 이동하기
import sys
from collections import deque
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
q = deque()
q.append([0, 0, 1])
visit = [[[0] * 2 for i in range(m)] for i in range(n)]
visit[0][0][1] = 1
while q:
a, b, w = q.popleft()
if a == n - 1 and b == m - 1:
return visit[a][b][w]
for i in range(4):
x = a + dx[i]
y = b + dy[i]
if 0 <= x < n and 0 <= y < m:
if s[x][y] == 1 and w == 1:
visit[x][y][0] = visit[a][b][1] + 1
q.append([x, y, 0])
elif s[x][y] == 0 and visit[x][y][w] == 0:
visit[x][y][w] = visit[a][b][w] + 1
q.append([x, y, w])
return -1
n, m = map(int, input().split())
s = []
for i in range(n):
s.append(list(map(int, list(input().strip()))))
print(bfs())
배열을 3차원으로 만들고, 배열의 맨 첫번째(i)값에는 벽을 부순 횟수 값을 가진다. (1이면 벽을 부수지 x , 0이면 벽을 하나 부숨).
부순 경우와 부수지 않은 경우를 각각 계산한다.
연습만이 살길이다...
'코테 > BOJ' 카테고리의 다른 글
백준 9663 [N-Queen] 파이썬 (0) | 2022.05.18 |
---|---|
백준 14503 [로봇 청소기] 파이썬 (0) | 2022.05.18 |
백준 1504 [특정한 최단 경로] 파이썬 (0) | 2022.05.17 |
백준 9935 [문자열 폭발] 파이썬 (0) | 2022.05.17 |
백준 11909 [배열 탈출] 파이썬 (0) | 2022.05.17 |