[백준 BOJ 8972] 미친 아두이노 (Python 파이썬)

미친 아두이노

골드3, Simulation, 구현

 

미친 아두이노 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	2725	842	617	28.303%

문제

요즘 종수는 아두이노를 이용해 "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는 종수가 게임이 끝나기 전 까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.

예제 입력 1 복사

4 5
I....
.....
.R.R.
.....
6

예제 출력 1 복사

.I...
.RR..
.....
.....

예제 입력 2 복사

9 10
..........
.........R
..........
R.........
R...I.....
R.........
..........
.........R
....R.....
5558888

예제 출력 2 복사

....I.....
....R.....
..........
..........
..........
..........
..........
..........
..........

예제 입력 3 복사

12 8
...I....
........
........
........
........
RR......
......RR
R......R
........
........
........
...R....
66445394444162

예제 출력 3 복사

kraj 11

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Regional Competition - Juniors 3번

• 문제를 번역한 사람: baekjoon

---

풀이

import sys
input = lambda : sys.stdin.readline().strip()

move = [(dx,dy) for dy in (1,0,-1) for dx in (-1,0,1)]

def solve(r, c, user_loc, krajs, queries):
    for X, query in enumerate(queries, 1):
        user_loc = [i+j for i,j in zip(user_loc, move[query])]
        if tuple(user_loc) in krajs:
            print(f"kraj {X}")
            exit()
        n_krajs = set()
        destroied = set()
        for kraj in krajs:
            n_kraj = []
            for uloc, kloc in zip(user_loc, kraj):
                diff = 0 if uloc==kloc else 1 if uloc>kloc else -1
                n_kraj.append(diff+kloc)
            if n_kraj == user_loc:
                print(f"kraj {X}")
                exit()
            robot = tuple(n_kraj)
            if robot in n_krajs:
                destroied.add(robot)
            else:
                n_krajs.add(robot)
        krajs = n_krajs-destroied
    board = [["."]*c for _ in range(r)]
    board[user_loc[1]][user_loc[0]] = "I"
    for kraj in krajs:
        board[kraj[1]][kraj[0]] = "R"
    for l in board:
        print(*l, sep="")

if __name__ == "__main__":
    r, c = map(int, input().split())
    jongsu, krajs = None, set()
    for rloc in range(r):
        line = input()
        if "I" in line:
            jongsu = (line.index("I"), rloc)
        for cloc, token in enumerate(line):
            if token == "R":
                krajs.add((cloc, rloc))
    solve(r, c, jongsu, krajs, queries = map(lambda x:int(x)-1, list(input())))

 

문제 설명

 RxC 크기의 보드를 Simulation 해야한다. 그 순서는 다음과 같다.

종수 -> 종료 여부 확인 -> 미친 아두이노 -> 종료 여부 확인 -> 폭발 여부 확인

위 순서에 맞게 구현만 하면 통과할 수 있는 간단한 문제이다.

 

초기 설정

 보드를 시뮬레이션 하는 문제지만 "."의 위치는 중요하지 않다. 주어진 모든 격자를 탐색하는 것은 효율적이지 않다. 종수와 아두이노의 위치와 움직임만 고려해도 충분하다. 입력을 받는 과정에서 처리한다.

 또한 아두이노는 같은 칸에 존재할 수 없다. set으로 중복을 처리해 준다.

 

방향에 따른 움직임 또한 배열에 선언해 준다.

input()으로 받은 보드는 위에서부터 y-index가 0이다. 따라서 1부터 9의 움직임은 (-1,1)부터 (1,-1)으로 설정하면 된다. move 리스트를 list comprehension으로 생성한다.

 

move = [(dx,dy) for dy in (1,0,-1) for dx in (-1,0,1)]

if __name__ == "__main__":
    r, c = map(int, input().split())
    jongsu, krajs = None, set()
    for rloc in range(r):
        line = input()
        if "I" in line:
            jongsu = (line.index("I"), rloc)
        for cloc, token in enumerate(line):
            if token == "R":
                krajs.add((cloc, rloc))
    solve(r, c, jongsu, krajs, queries = map(lambda x:int(x)-1, list(input())))

r과 c를 입력받고, 종수와 krajs 집합을 선언한다. 이후 최상단 줄부터 입력을 받고, 종수("I")와 아두이노("R")의 존재 여부를 확인해 jongsu, krajs를 갱신한다.

방향에 따른 움직임이 주어져 있다. 방향을 0부터 시작하게 세팅했다.

이후 solve함수에 인자로 행렬의 크기와 종수 위치, 아두이노 위치, 움직임을 나타내는 명령어(queries)를 받아 시뮬레이션을 진행한다.

 

시뮬레이션

매 이동마다 종료 여부 확인이 필요하다. enumerate로 라운드와 이동 방향을 뽑아온다.

이제 위에서 언급한 순서로 구현을 진행한다.

유저 이동

이동은 매우 쉽게 표현할 수 있다. query를 move의 index로 넣어만 주면 이동 시 변화하는 dr, dc를 얻어낼 수 있다. 이를 현재 위치에서 더해주면 다음 위치로 이동이 가능하다.

이동 후에는 종료 여부 확인을 위해 현재 아두이노 위치 중 user_loc이 존재하는지만 확인하면 끝이다. 이 과정에서 모든 아두이노를 탐색하지 않기 위하여 앞에서 set을 활용했다.

        user_loc = [i+j for i,j in zip(user_loc, move[query])]
        if tuple(user_loc) in krajs:
            print(f"kraj {X}")
            exit()

 

아두이노 이동

아두이노의 이동은 순회하며 유저와 동일한 과정을 취해주면 된다. (파이썬의 Counter 라이브러리를 활용하면 더 쉽게 구현이 가능하다.)

이동 방향 결정은 유저와 아두이노의 위치를 비교하면 된다.

1. 유저의 x좌표가 아두이노 x좌표보다 큰 경우 -> 아두이노를 x축으로 1만큼 이동

2. 유저의 x좌표가 아두이노 x좌표와 같은 경우 -> 아두이노를 이동하지 않음

3. 유저의 x좌표가 아두이노 x좌표보다 작은 경우 -> 아두이노를 x축으로 1-만큼 이동

y축도 동일하게 이동방향을 정할 수 있다.

얻어진 이동방향으로 아두이노를 이동시키고, 종료조건을 확인한다. 이후 동일한 좌표에 아두이노가 있으면 destroied에, 그렇지 않으면 차기 krajs에 넣어준다.

그 다음 파괴되지 않은 아두이노로 다음 루프를 진행한다.

        for kraj in krajs:
            n_kraj = []
            for uloc, kloc in zip(user_loc, kraj):
                diff = 0 if uloc==kloc else 1 if uloc>kloc else -1
                n_kraj.append(diff+kloc)
            if n_kraj == user_loc:
                print(f"kraj {X}")
                exit()
            robot = tuple(n_kraj)
            if robot in n_krajs:
                destroied.add(robot)
            else:
                n_krajs.add(robot)
        krajs = n_krajs-destroied

 

결과 출력

루프가 종료되면 유저와 아두이노들의 최종 위치가 user_loc, krajs에 저장된다. RxC 보드를 생성하고 해당 위치에 유저와 아두이노를 표시한 후 출력하면 문제 풀이가 완료된다.

    board = [["."]*c for _ in range(r)]
    board[user_loc[1]][user_loc[0]] = "I"
    for kraj in krajs:
        board[kraj[1]][kraj[0]] = "R"
    for l in board:
        print(*l, sep="")

---

단순 시뮬레이션 문제임에도 최적화 방식에 따라서 시간의 차이가 발생한다. 특히 로봇의 위치가 변화할 수록 개수가 줄어드는 이번 문제에서 모든 좌표를 탐색하는 것과 아닌것의 차이는 확연하다. 문제를 풀 때 필요한 최소 정보만 활용하여 최적화하면 효율성을 최대화 할 수 있다.