[백준]16197: 두 동전

BFS

두 동전

BFS문제이지만 이동 해야 할 것이 2개 이상일때는 다음의 전략으로 가자!
1. 먼저, 동전이 이동할 때 서로 구분되어야 하는가?
-> 구분해야 한다면, 큐에 각 동전을 매개변수로 따로 넣어주고 아니라면 큐에 한번에 넣어준다.
2. 방문 배열 -> 여기서는 동전이 두개 이므로 4차원 배열로 둔다.
3. 둘 다 범위안에 있다. 그런데 하나의 동전이 벽에 닿아도 다른 동전은 이동할 수 있다. -> rnx = rx 그대로 두기
4. 동전 하나만 범위를 벗어나 떨어질 때 -> 이 문제에서의 출력조건 -> 하나 더 이동해서 출력
5. 두 동전 모두 범위를 벗어나 떨어질 때 -> 무시

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(sys.stdin.readline().rstrip()))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
	while q:
    		# 이동방향에 따라 큐에 들어가는 것이 다르므로 한 번 이동할 때 갈 수 있는 방향을 모두 본다 
		for _ in range(len(q)):
			rx, ry, bx, by, cnt = q.popleft()
            		# 이동 횟수가 10 이상이면 -1
			if cnt > 10:
				return -1
                	# 방문처리 
			visited[rx][ry][bx][by] = True
			for i in range(4):
				rnx = rx + dx[i]
				rny = ry + dy[i]
				bnx = bx + dx[i]
				bny = by + dy[i]
				# 둘 다 범위 내에 있는 경우
				if 0 <= rnx < n and 0 <= rny < m and 0 <= bnx < n and 0 <= bny < m:
                			# 하나가 벽이여도 다른건 계속 가야함 
					if graph[rnx][rny] == '#':
						rnx = rx
						rny = ry
					if graph[bnx][bny] == '#':
						bnx = bx
						bny = by
                        		# 카운트 증가 시켜 큐에 넣기 
					if not visited[rnx][rny][bnx][bny]:
						visited[rnx][rny][bnx][bny] = True
						q.append((rnx, rny, bnx, bny, cnt +1))
                       		# 하나만 떨어지면 밀어서(cnt+1) 출력
				elif 0 <= rnx < n and 0 <= rny < m:
					return cnt+1
                    		# 마찬가지
				elif 0 <= bnx < n and 0 <= bny < m:
					return cnt+1
                    		# 둘다 떨어지면 없었던 일로 하자 
				else:
					continue
	return -1
q = deque()
start = []
for i in range(n):
	for j in range(m):
		if graph[i][j] == 'o':
			start.append((i, j))
            # 'o' 인 좌표를 큐에 넣어준다 
q.append((start[0][0], start[0][1], start[1][0], start[1][1], 0))
visited =[[[[False for _ in range(m)] for _ in range(n)]for _ in range(m)]for _ in range(n)]
print(bfs())