백준 16197 - 두 동전

백준 16197 - 두 동전

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

두 동전을 동시에 4방향으로 이동가능하며 두 동전 중 하나만 떨어뜨려야하는 문제이다. 중간에 멈출 수 있는 bfs를 이용하였다. 실수한 부분이 벽일 경우 처리이다. 이부분에서 dfs인 경우 백트랙킹을 사용해서 이전 좌표로 돌아가면 됐다. bfs로 백트랙킹을 사용해 보지 않아서 방법을 잘 몰랐다.. 삽질 끝에 다음 탐색 좌표를 현재 좌표로 설정해 주면 되는 간단한 방법이 있었다...
아래는 예시이다.

0 1
0 1

1 벽 ,0 은 내가 현재 있는 위치(1,1)에서  4방향으로 갈 수 있으며 만약 벽을 만나면 board[next_r][next_c] == 1 현재 위치로 다시 돌아 와야한다.
방법은  board[next_r][next_c] == 1(벽을 만날 경우) 다음 탐색할 좌표를 현재 좌표로 넣어주면된다. 

if board[next_r][next_c] == 1:
    next_r = r
    next_c = c
    q.append((next_r, next_c))
이런식으로 해주면된다.

작성한 코드는

from collections import deque

N, M = map(int,input().split())

board = []

dr = [1,-1,0,0]
dc = [0,0,1,-1]

visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]
## 'o' - 동전, '.' - 빈 칸  , '#' - 벽
for i in range(N):
    data = list(input())
    board.append(data)

coin_pos = []

for i in range(N):
    for j in range(M):
        if board[i][j] == 'o':
            coin_pos.append((i,j))


def bfs():
    q = deque()
    q.append((coin_pos[0][0], coin_pos[0][1], coin_pos[1][0], coin_pos[1][1],0))
    cnt= 0 
    visited[coin_pos[0][0]][coin_pos[0][1]][coin_pos[1][0]][coin_pos[1][1]] = True
    flag = 0
    answer = 0
    while q:
        pos = q.popleft()
        # pos 0,1 -> r1,c1  
        # pos 1,2 -> r2,c2
        if pos[4] >= 10:
            return -1
        for i in range(4):
            #동전 1
            next_r_1 = pos[0] + dr[i]
            next_c_1 = pos[1] + dc[i]
            #동전 2
            next_r_2 = pos[2] + dr[i]
            next_c_2 = pos[3] + dc[i]

            if 0<=next_r_1 <N and 0<=next_c_1<M and 0<=next_r_2<N and 0<=next_r_2<N and 0<=next_c_2<M:
                if not visited[next_r_1][next_c_1][next_r_2][next_c_2]:
                    if board[next_r_1][next_c_1] == "#":
                        next_r_1, next_c_1 = pos[0], pos[1]
                    if board[next_r_2][next_c_2] == "#":
                        next_r_2, next_c_2 = pos[2], pos[3]
                    visited[next_r_1][next_c_1][next_r_2][next_c_2] = True
                    q.append((next_r_1,next_c_1,next_r_2,next_c_2, pos[4]+1))
            elif 0<=next_r_2<N and 0<=next_r_2<N and 0<=next_c_2<M: 
                return pos[4] + 1
            elif 0<=next_r_1 <N and 0<=next_c_1<M:
                return pos[4] + 1
            else:
                continue


print(bfs())