https://www.acmicpc.net/problem/16197
16197번: 두 동전N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고,www.acmicpc.net
bfs를 두 동전으로 하면 된다
방문처리를 안하고도 풀 수있지만, 시간이 어마어마하계 걸린다.
나는 따로 방문배열을 만든 것이 아니라, set에 각 동전에 위치를 넣고, 비교하는 방식으로 했다.
60%에서 계속 에러가 나서 고민했는데, 최대10번까지 허용인데 11번까지 허용해서 그랬다.
즉, 11번하면 정답인 경우에는 -1을 출력해야한다.
더러운문제였다.
코드
from collections import dequeimport sysinput=sys.stdin.readlinecoins=[]arr=[]
n,m=map(int,input().split())for i in range(n): tmp=list(input().rstrip())
arr.append(tmp) for j in range(m): if tmp[j]=='o':
coins.append(i) coins.append(j)
move=[[-1,0],[1,0],[0,-1],[0,1]]s=set()q=deque()q.append(coins)
s.add(tuple(coins))coins.append(0)while q: cx1,cy1,cx2,cy2,w=q.popleft()
if w>9: print(-1) exit() for dx,dy in move:
nx1,ny1,nx2,ny2=cx1+dx,cy1+dy,cx2+dx,cy2+dy
if (0<=nx1<n and 0<=ny1<m)^(0<=nx2<n and 0<=ny2<m): #동전중 하나만 떨어졌으면
print(w+1) #걸린시간출력 후 종료 exit()
elif (0<=nx1<n and 0<=ny1<m)and(0<=nx2<n and 0<=ny2<m): #둘다arr안에 있으면
if arr[nx1][ny1]=='#':#벽이면 그냥 처음으로 nx1,ny1=cx1,cy1
if arr[nx2][ny2]=='#': nx2,ny2=cx2,cy2
if (nx1,ny1,nx2,ny2) not in s:
q.append(( nx1,ny1,nx2,ny2,w+1))
s.add(( nx1,ny1,nx2,ny2))print(-1)