[BOJ] 2206

문제

me

1. bfs
   최단 거리, 인접 만 보고 bfs를 했다.

import sys
from collections import deque
input = sys.stdin.readline
n,m=map(int,input().split())
boxes=[list(input().strip()) for _ in range(n)]
routes=[[0]*m for _ in range(n)]
def bfs():
    queue=deque([(False,0,0)]) # 벽 뿌셨는지 여부, x, y
    boxes[0][0]=-1
    routes[0][0]=1
    dx=[-1,0,+1,0]
    dy=[0,+1,0,-1]
    while queue:
        broked,x,y=queue.popleft()
        if x==n-1 and y==m-1 : break
        if x==3 and y==4: print(broked,x,y,queue)
        for i in range(4):
            nx=x+dx[i]; ny=y+dy[i];
            if -1 < nx < n and -1 < ny < m: # 범위 내
                if boxes[nx][ny] == '0':  # 0일때만 무조건 이동
                    boxes[nx][ny]=-1
                    routes[nx][ny] = (x,y)#routes[x][y] + 1
                    queue.append((broked, nx, ny))
                elif not broked and boxes[nx][ny]=='1': # 한번도 부서진 적 없어서 부서도 됨. 1도 이동
                        boxes[nx][ny] = -1
                        routes[nx][ny]= (x,y)#routes[x][y]+1
                        queue.append((True,nx,ny))

    print(routes[n-1][m-1] if routes[n-1][m-1]!=0 else -1)
bfs()
for box in boxes:
    print(box)
print('--')
for route in routes:
    print(route)

queue가 비게 되면 종료가 된다. 다른 길이 있는데도 그 길이 최단 거리라고 여기고 종료가 된다.
bfs는 가장 먼저 도달하는게 최단 거리라는 원칙이 있기에 문제 해결과 안맞다고 생각했다.

2. dfs
   모든 길을 가보고 가장 최단을 찾아야 겠다는 생각을 했다.

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().split())

boxes=[list(map(int,input().strip())) for _ in range(n)]
#for box in boxes: print(box)
routes=[[0]*m for _ in range(n)]
routes[0][0]=1

dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(queue):
    global min_route
    broke,x,y=queue.popleft()
    #print(broke,x,y)
    if x==n-1 and y==m-1:
        min_route=min(routes[x][y],min_route)
        #print(min_route)
        #for route in routes:print(route)
        return
    #print('done')
    for i in range(4):
        nx=x+dx[i]; ny=y+dy[i];
        #print(nx,ny)
        if -1 < nx < n and -1 < ny < m: # 범위 내
            if boxes[nx][ny] == 0: #'0':  # 0일때만 무조건 이동
                boxes[nx][ny]=-1
                routes[nx][ny] = routes[x][y] + 1
                queue.append((broke, nx, ny))
                dfs(queue)
                #print('0 out',nx,ny,queue)
                boxes[nx][ny]=0 #'0'
                routes[nx][ny]=0
                #queue.pop()
            elif not broke and boxes[nx][ny]==1: #'1': # 한번도 부서진 적 없어서 부서도 됨. 1도 이동
                boxes[nx][ny] = -1
                routes[nx][ny]= routes[x][y]+1
                queue.append((True,nx,ny))
                dfs(queue)
                #print('1 out',nx,ny,queue)
                boxes[nx][ny] = 1 #'1'
                routes[nx][ny] = 0
                #queue.pop()

min_route=int(1e9)
dfs(deque([[False,0,0]]))
print(min_route)

나중에 다듬으려고 사용한 변수와 배열이 많다.
어쨌든 이것도 안됐다.. queue가 끊임없이 쌓인다..

둘다 동일하게 참고의 반례인

13 13
0100011011000
0001001010000
0000100001000
1100010101011
1111101111000
1011010001001
0100001001001
0100111010001
0101010000100
0001110100000
0000001000100
1010001000111
1001000100000

정답 : 27

1번은 -1이 출력되고, 2번은 무한루프를 도는 문제가 발생한다..
8ㅅ8... 꼭 풀고 싶었는데 시간이 너무 늘어진다..

solution

참고

from collections import deque

row, col = map(int, input().split())
graph = [list(map(int, input())) for _ in range(row)]
visited = [[[0] * 2 for _ in range(col)] for _ in range(row)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def Bfs(start_x, start_y, iscrash, visited, graph):
    #crash 0: 벽안부시고 가는경우, 1: 부신 경우
    queue = deque()
    queue.append((start_x, start_y, iscrash))
    visited[start_x][start_y][iscrash] = 1

    while queue:
        cur_x, cur_y, iscrash = queue.popleft()
        if cur_x == row - 1 and cur_y == col - 1:
            return visited[cur_x][cur_y][iscrash]
        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x <= -1 or next_x >= row or next_y <= -1 or next_y >= col:
                continue
            # 벽 안부수고 이동
            if graph[next_x][next_y] == 0 and visited[next_x][next_y][iscrash] == 0:
                queue.append((next_x, next_y, iscrash))
                visited[next_x][next_y][iscrash] = visited[cur_x][cur_y][iscrash] + 1
            # 벽 부수고 이동
            if graph[next_x][next_y] == 1 and iscrash == 0:
                queue.append((next_x, next_y, iscrash + 1))
                visited[next_x][next_y][iscrash + 1] = visited[cur_x][cur_y][iscrash] + 1

    return -1

print(Bfs(0, 0, 0, visited, graph))

3차원 배열을 만드는데, visit[x][y][i]에서 i가 0이라면 벽을 한번 뚫은 상태이고,
1이라면 벽을 뚫을 수 있는 상태를 나타낸다.
bfs을 돌려주는데 벽을 뚫을 수 있는 상태이고, 벽을 만난다면 벽을 뚫어주고 +1을 해준다.
아직 방문하지 않았고 벽이 아니라면 또한 +1을 해준다.

.. 이해는 스터디에서 하는 걸로..