문제 링크 : https://www.acmicpc.net/problem/13460
7시간동안 풀었다. 결국 내 스스로 맞추는데 성공했다..
이 문제의 핵심은 2개라고 생각한다.
- 빨간 공, 파란 공을 굴리는 함수 move 구현
- BFS 에서 visit 처리를 어떻게 해줄 것인지
이 2개가 까다로워서 그렇지 전체적인 틀은 결국 BFS 문제다. 게임 보드를 기울이면 벽을 만날 때까지 그 방향으로 공들이 굴러간다. 고려해야 할 것은 굴리다가 "빨간 공과 파란 공이 부딪히는 경우"다.
예를 들어 [# . R B . #]순으로 배치 되어있을 때, 오른쪽으로 보드를 기울이면 [# . . R B #] 이 되어야 한다. (R : 빨간 공, B : 파란 공)
1. move 함수 구현
위 케이스에서 나는 파란 공이 "우선 순위에 있다"(priority) 라고 정의했다. 둘 다 옮겨줘야 하는데 만약 빨간 공을 먼저 옮기고 파란 공을 옮기면, 파란공이 벽에 부딪혀 더 이상 움직이지 않을 때, 빨간 공이 파란 공 때문에 더 움직여야 하는데 더 이상 못움직이는 경우가 발생하게 된다. 파란 공을 먼저 옮겨주면 이런 문제가 발생하지 않게 된다.
priority 조건에 따라서 코드를 작성해서 move 함수를 완성했다. 다 풀고나서 다른 사람들의 풀이를 참고해봤는데, 이렇게 우선순위를 따질 필요가 없이 그냥 벽을 만날 때까지 빨간 공과 파란 공을 모두 옮겨주고, 두 공이 겹치게 된다면 더 많이 움직인 공을 한칸 뒤로 물러서게 하는 방식으로 많이 풀더라.. 그게 더 쉬운 것 같다.
2. visit 처리
처음에 redVisit 과 blueVisit 두 개의 방문처리 리스트를 만들고, if redVisit and blueVisit 인 경우 탐색을 중단하도록 로직을 구성했다. 나름 괜찮은 로직이라고 생각했지만 오랜 고민 뒤에 반례를 발견 했다.
보드가 다음과 같이 구성 되어있을 때, ( 좌 -> 하 -> 우 -> 하 ) 로 이동하면 4회에 빨간 공을 구멍에 넣을 수 있다. 하지만 ( 좌 -> 하 ) 에서 redVisit[1][4] 과 blueVisit[3][2] 가 모두 True 인 상태로 다시 (-> 우) 를 진행한다면 탐색을 계속할 수 없게 된다.
빨강과 파랑을 모두 방문처리 해준다는 생각은 맞았다. 하지만 visit[redX][redY][blueX][blueY] 와 같이 4차원 리스트에 담아 동시에 생각하는게 더 맞는 생각이었다.
4차원 방문 리스트 처리 방법 2 가지
[방법 1] 직접 4차원 리스트를 생성한다.
visit = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)][방법 2] 4차원 tuple로 방문한 좌표를 리스트에 담는다.
visit.append((rx, ry, bx, by)) ... if (nextRX, nextRY, nextBX, nextBY) in visit: ...
파이썬 코드
import sys import copy from collections import deque N, M = map(int, sys.stdin.readline().split()) graph = [] startRed = (0, 0) startBlue = (0, 0) direction = [(-1, 0), (1, 0), (0, -1), (0, 1)] for i in range(N): graph.append(list(sys.stdin.readline().strip())) for j in range(M): if graph[i][j] == 'R': graph[i][j] = '.' startRed = (i, j) elif graph[i][j] == 'B': graph[i][j] = '.' startBlue = (i, j) # 보드 기울이기 # 예를들어 R B 순으로 있는데 오른쪽으로 기울인다면 B가 우선순위가 되어야 한다. def move(red, blue, d): board = copy.deepcopy(graph) board[red[0]][red[1]] = 'R' board[blue[0]][blue[1]] = 'B' stopRed = False stopBlue = False priority = '' gap = (red[0]-blue[0], red[1]-blue[1]) # 상 하 좌 우 if d == 0: if gap[0] > 0: priority = 'BLUE' else: priority = 'RED' elif d == 1: if gap[0] > 0: priority = 'RED' else: priority = 'BLUE' elif d == 2: if gap[1] > 0: priority = 'BLUE' else: priority = 'RED' elif d == 3: if gap[1] > 0: priority = 'RED' else: priority = 'BLUE' while True: if stopRed and stopBlue: break nRed = red nBlue = blue # 먼저 현재 구슬자리를 비워놓음 if not stopRed: board[red[0]][red[1]] = '.' nRed = red[0] + direction[d][0], red[1] + direction[d][1] if not stopBlue: board[blue[0]][blue[1]] = '.' nBlue = blue[0] + direction[d][0], blue[1] + direction[d][1] # 우선권이 빨강일 때 if priority == 'RED': # 빨강 처리 if not stopRed: nextRedValue = board[nRed[0]][nRed[1]] if nextRedValue == '.': red = nRed board[red[0]][red[1]] = 'R' elif nextRedValue == '#': board[red[0]][red[1]] = 'R' stopRed = True elif nextRedValue == 'O': red = 'GOAL' stopRed = True elif nextRedValue == 'B': board[red[0]][red[1]] = 'R' stopRed = True # 파랑 처리 if not stopBlue: nextBlueValue = board[nBlue[0]][nBlue[1]] if nextBlueValue == '.': blue = nBlue board[blue[0]][blue[1]] = 'B' elif nextBlueValue == '#': board[blue[0]][blue[1]] = 'B' stopBlue = True elif nextBlueValue == 'O': blue = 'GOAL' stopBlue = True elif nextBlueValue == 'R': board[blue[0]][blue[1]] = 'B' stopBlue = True # 우선권이 파랑일때 elif priority == 'BLUE': # 파랑 처리 if not stopBlue: nextBlueValue = board[nBlue[0]][nBlue[1]] if nextBlueValue == '.': blue = nBlue board[blue[0]][blue[1]] = 'B' elif nextBlueValue == '#': board[blue[0]][blue[1]] = 'B' stopBlue = True elif nextBlueValue == 'O': blue = 'GOAL' stopBlue = True elif nextBlueValue == 'R': board[blue[0]][blue[1]] = 'B' stopBlue = True # 빨강 처리 if not stopRed: nextRedValue = board[nRed[0]][nRed[1]] if nextRedValue == '.': red = nRed board[red[0]][red[1]] = 'R' elif nextRedValue == '#': board[red[0]][red[1]] = 'R' stopRed = True elif nextRedValue == 'O': red = 'GOAL' stopRed = True elif nextRedValue == 'B': board[red[0]][red[1]] = 'R' stopRed = True return red, blue turn = 0 answer = 100 # BFS 시작 (빨간 공 위치, 파란 공 위치, 턴 횟수, 빨강 방문, 파랑 방문) visit = [[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)] q = deque() q.append(( (startRed[0], startRed[1]), (startBlue[0], startBlue[1]), turn)) visit[startRed[0]][startRed[1]][startBlue[0]][startBlue[1]] = True go = True while q: nowRed, nowBlue, t = q.popleft() if t >= 10: break # 상하좌우 탐색 for i in range(4): nextRed, nextBlue = move(nowRed, nowBlue, i) if nextRed == 'GOAL' and nextBlue != 'GOAL': answer = min(answer, t + 1) go = False break elif nextRed == 'GOAL' and nextBlue == 'GOAL': continue elif nextRed != 'GOAL' and nextBlue != 'GOAL': if not visit[nextRed[0]][nextRed[1]][nextBlue[0]][nextBlue[1]]: q.append((nextRed, nextBlue, t + 1)) visit[nextRed[0]][nextRed[1]][nextBlue[0]][nextBlue[1]] = True elif nextRed != 'GOAL' and nextBlue == 'GOAL': continue if not go: break if answer == 100: print(-1) else: print(answer)
