백준 2206 [벽 부수고 이동하기] 파이썬

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

# 백준 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 파이썬)

이 분의 풀이이다.

# 백준 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이면 벽을 하나 부숨).

부순 경우와 부수지 않은 경우를 각각 계산한다.

 

 

 

 

 

연습만이 살길이다...