[Python/BOJ] 8972. 미친 아두이노

https://www.acmicpc.net/problem/8972

8972번: 미친 아두이노

문제

요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다.

게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다.

1. 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
2. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
3. 미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
4. 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
5. 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.

종수의 시작 위치, 미친 아두이노의 위치, 종수가 움직이려고 하는 방향이 주어진다. 입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 작성하시오. 중간에 게임에서 지게된 경우에는 몇 번째 움직임에서 죽는지를 구한다.

입력

첫째 줄에 보드의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, 보드의 상태이다. '.'는 빈 칸, 'R'은 미친 아두이노, 'I'는 종수의 위치를 나타낸다.

마지막 줄에는 길이가 100을 넘지않는 문자열이 주어지며, 종수가 움직이려고 하는 방향이다. 5는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.

 

보드를 벗어나는 입력은 주어지지 않는다.

출력

중간에 게임이 끝나는 경우에는 "kraj X"를 출력한다. X는 종수가 게임이 끝나기 전 까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

# 1. 게임 종료 함수 정의
def end_game() :
    # 1-1. 결과 출력
    print(f'kraj {idx}')
    # 1-2. 시스템 종료
    exit()
# 2. 종수 이동 함수 정의
def move_jongsoo(dir) :
    global jongsoo
    next_jongsoo = [jongsoo[0] + dirs[dir][0], jongsoo[1] + dirs[dir][1]]
    # 2-1. 이동 방향에 아두이노가 있을 경우
    if board[next_jongsoo[0]][next_jongsoo[1]] == 'R': end_game() # 게임 종료 함수 실행
    # 2-2. 보드 변환
    board[jongsoo[0]][jongsoo[1]], board[next_jongsoo[0]][next_jongsoo[1]] = '.', 'I'
    # 2-3. 종수 위치 인덱스 재설정
    jongsoo = next_jongsoo
    return
# 3. 미친 아두이노 이동 함수 정의
def craze_arduino(x, y) :
    global arduino
    # 3-1. 최소 거리를 갖는 방향 찾기
    distance = [float('inf')]
    for dir_x, dir_y in dirs[1:] :
        nx, ny = x + dir_x, y + dir_y
        distance.append(abs(jongsoo[0] - nx) + abs(jongsoo[1] - ny))
    best_dir = distance.index(min(distance))
    nx, ny = x + dirs[best_dir][0], y + dirs[best_dir][1]
    # 3-2. 아두이노 이동에 따른 보드 위치 재설정
    if board[x][y] == 'R' : board[x][y] = '.' # 현재 위치가 R일 경우
    elif board[x][y][:-1] == 'R' : board[x][y] = 'R' # 현재 위치가 RR 일 경우
    # 3-3. 다음 위치가 종수 위치일 경우 종료
    if board[nx][ny] == 'I' :
        end_game()
    # 3-4. 다음 위치가 빈 칸일 경우
    elif board[nx][ny] == '.' :
        board[nx][ny] = 'R'
    # 3-5. 아두이노 위치일 경우
    else :
        board[nx][ny] += 'R'
    return

r, c = map(int, input().split())
board = [list(map(str, input().rstrip())) for _ in range(r)]
# 4. 이동 방향 리스트 정의
dirs = [[], (1, -1), (1, 0), (1, 1), (0, -1), (0, 0), (0, 1), (-1, -1), (-1, 0), (-1, 1)]
# 5. 종수 이동방향 리스트화
order = [0] + list(map(int, input().rstrip()))
# 6. 종수 위치와 아두이노 위치 구하기
arduino = []
for i in range(r) :
    for j in range(c) :
        # 종수 위치일 경우
        if board[i][j] == 'I' : jongsoo = [i, j]
        # 아두이노일 경우
        elif board[i][j] == 'R' : arduino.append([i, j])
# 7.
for idx, dir in enumerate(order) :
    if idx == 0 : continue
    # 7-1. 종수 이동
    move_jongsoo(dir)
    # 7-2.
    for x, y in arduino :
        # 미친 아두이노 이동 함수 실행
        craze_arduino(x, y)
    # 7-3. 아두이노 위치 재설정
    sub_arduino = []
    for i in range(r):
        for j in range(c):
            # 해당 인덱스에 아두이노 개수가 2개 이상일 경우 아두이노 파괴
            if len(board[i][j]) >= 2: board[i][j] = '.'
            # 아두이노가 1개만 있을 경우 다음 아두이노 위치 리스트에 저장
            elif board[i][j] == 'R' : sub_arduino.append([i, j])
    arduino = sub_arduino.copy()

# 8. 보드 출력
for line in board :
    print(''.join(line))