요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다.
게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다.
먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다. 미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다. 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다. 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다. 종수의 시작 위치, 미친 아두이노의 위치, 종수가 움직이려고 하는 방향이 주어진다. 입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 작성하시오. 중간에 게임에서 지게된 경우에는 몇 번째 움직임에서 죽는지를 구한다.
다음 R개 줄에는 C개의 문자가 주어지며, 보드의 상태이다. '.'는 빈 칸, 'R'은 미친 아두이노, 'I'는 종수의 위치를 나타낸다.
마지막 줄에는 길이가 100을 넘지않는 문자열이 주어지며, 종수가 움직이려고 하는 방향이다. 5는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.
보드를 벗어나는 입력은 주어지지 않는다.
출력
중간에 게임이 끝나는 경우에는 "kraj X"를 출력한다. X는 종수가 게임이 끝나기 전 까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.
입력 예시
4 5
I....
.....
.R.R.
.....
6
출력 예시
.I...
.RR..
.....
.....
풀이
문제에서 제시한 조건을 그대로 구현하면 된다. 종수와 아두이노 좌표들을 관리하며, 조건에 따라 각 움직임을 좌표에 반영하자. 이 때 아두이노들의 최적의 움직임(종수와 가장 가까운 방향으로 움직이기) 및 충돌 관리(둘 이상의 아두이노가 한 좌표에 위치할 경우)를 신경써서 구현하면 된다. 본인의 경우 차집합 기능을 지원하는 set 자료구조로 해결할 수 있었지만, 더 효율적인 해결 방안 역시 존재하리라 믿는다.
풀이 코드
from collections import defaultdict
import sys
input = sys.stdin.readline
MAX = float('inf')
dr = [1, 1, 1, 0, 0, 0, -1, -1, -1]
dc = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
R, C = map(int, input().split())
map_list = [list(input().strip()) for _ in range(R)]
arduino_list = set()
tr, tc = -1, -1
for r in range(R) :
for c in range(C) :
if map_list[r][c] == 'I' :
tr, tc = r, c
elif map_list[r][c] == 'R' :
arduino_list.add((r, c))
move_set = input().strip()
flg = True
for idx, move in enumerate(move_set) :
move = int(move) - 1
tr, tc = tr + dr[move], tc + dc[move]
next_arduino_list = set()
crashed = set()
for r, c in arduino_list :
br, bc, bdist = -1, -1, MAX
for k in range(9) :
_br, _bc = r + dr[k], c + dc[k]
if abs(_br - tr) + abs(_bc - tc) < bdist :
br, bc, bdist = _br, _bc, abs(_br - tr) + abs(_bc - tc)
if tr == br and tc == bc :
flg = False
break
if (br, bc) in next_arduino_list :
crashed.add((br, bc))
else :
next_arduino_list.add((br, bc))
if not flg :
break
arduino_list = next_arduino_list - crashed
if not flg :
print("kraj {}".format(idx+1))
else :
result = [['.']*C for _ in range(R)]
result[tr][tc] = 'I'
for r, c in arduino_list :
result[r][c] = 'R'
for _result in result :
print(''.join(_result))
