https://www.acmicpc.net/problem/16954
16954번: 움직이는 미로 탈출욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽www.acmicpc.net
처음에는 그래프를 통한 bfs를 생각했지만, 배열도 만들지 않고 풀었다.
아이디어만 알면 진짜 간단하다.
먼져, 벽의 위치를 집합에 넣는다.
이후 7번 (어느 벽이던 7번 턴이 지나면 사라지므로) 반복문을 돌며 bfs를 하는데,
다음 노드를 큐에 끝에 넣지 않고 임시집합에 넣는다.
그후, 벽을 아래로 한칸식 이동시킨 후에,
임시집합에서 벽을 빼주어 안겹치는 노드를 구한 후,
다시반복문을 이어간다.
만일 7번을 버티면 무조건 나갈수 있고, 아니면 못나가는거다.
집합에도 한줄반복물을 쓸 수 있다는 것을 알게 되었다.
코드
import sysinput=sys.stdin.readlinefrom collections import deque
move=[[-1,0],[1,0],[0,-1],[0,1],[1,1],[1,-1],[-1,1],[-1,-1],[0,0]]wall=set()
for i in range(8): tmp=list(input().rstrip()) for j in range(8):
if tmp[j]=='#': wall.add((i,j))q=deque([(7,0)])
for _ in range(7): qq=set() while q: cx,cy=q.popleft()
for a,b in move: nx,ny=cx+a,cy+b
if 0<=nx<8 and 0<=ny<8 and(nx,ny) not in wall:
qq.add((nx,ny))
wall={(x[0]+1,x[1]) for x in wall if x[0]<7} #벽 이동
if not wall: #벽이없으면 무조건 갈 수 있다. print(1) exit()
qq-=wall #벽이랑 곂치는 부분 제외하기 if not qq: #더 나아갈 부분이 없으면 못가는거 print(0)
exit() for qqq in qq: q.append(qqq)print(1)