(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개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.

 

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

 

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

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

 

---

• 풀이 :

구현 문제였습니다.

 

문제에서 주의해야 할 점은

종수의 아두이노가 움직이고 난 후 미친 아두이노가 움직이는 순서는 있지만 

각각의 아두이노가 움직이는 것엔 순서가 없다는 것입니다.

 

따라서 1회 명령을 실행한 이후 한번에 좌표들을 갱신해주어야 합니다.

 

처음에는 board의 값을 직접 변경하며 실제 흐름을 구현하였으나 

아두이노의 좌표들만을 담아놓은 set을 사용하여 정답을 출력할 때만 board를 구현하였습니다.

 

알고리즘의 흐름은 문제에서 요구하는 조건의 흐름대로 구현하였으며 주석을 통해 확인하시면 될 것 같습니다.

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

R, C = map(int,input().split())
dx = [0, 1, 1, 1, 0, 0, 0, -1, -1 ,-1]
dy = [0, -1, 0, 1, -1, 0, 1, -1, 0, 1]
arduino  = set()

board = [list(input().strip()) for _ in range(R)]

# 아두이노들의 좌표를 찾는다.
for i in range(R):
    for j in range(C):
        if board[i][j] == "I":
            robot = [i,j]
        elif board[i][j] == "R":
            arduino.add((i,j))

# 명령 실행
for cnt, command in enumerate(input().strip()):
    
    # 종수가 주어진 명령에 따라 아두이노를 이동함
    command = int(command)
    robot[0] += dx[command]
    robot[1] += dy[command]
    
    # 이동한 칸에 미친아두이노가 있는 경우 종료
    if (robot[0],robot[1]) in arduino:
        print("kraj",cnt+1)
        exit()
        
    move = set() # 이동한 미친 아두이노의 좌표
    crushed = set() # 충둘이 일어난 미친 아두이노의 좌표


    for x,y in arduino:
        m = [5, 201] # 최소 거리가 되는 방향을 저장
        
        # 8방향 중 거리가 최소가 되는 방햐 찾음
        for j in range(1,10):
            ax = x + dx[j]
            ay = y + dy[j]
            distance = abs(ax-robot[0]) + abs(ay-robot[1])
            if distance < m[1]:
                m = [j,distance]

        # 찾은 방향으로 이동
        x += dx[m[0]]
        y += dy[m[0]]
        if [x,y] == robot: # 종수의 아두이노를 잡은 경우
            print("kraj", cnt + 1)
            exit()
        elif (x,y) in move: # 미친 아두이노끼리 충돌한 경우
            crushed.add((x,y)) 
        else: # 정상적으로 이동할 수 있는 경우
            move.add((x,y))
            
    # 충돌이 일어난 미친 아두이노의 좌표를 이동한 미친 아두이노 좌표 집합에서 삭제        
    for x,y in crushed:
        move.remove((x,y))
    arduino = move # 이동 완료한 아두이노의 좌표를 갱신해줌


# 출력을 위해 board를 새로 만들고 아두이노들의 좌표를 표시
board = [["." for _ in range(C)] for _ in range(R)]
for x,y in arduino:
    board[x][y] = "R"
board[robot[0]][robot[1]] = "I"
for i in range(R):
    print(''.join(board[i]))