[BOJ]8972 미친 아두이노

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

8972번: 미친 아두이노

풀이

논리는 어렵지 않은 시뮬레이션 문제인데 시간제한이 1초여서 시간초과에 걸리지 않을까 고민을 많이 했던 문제였다. 먼저 편의를 위해서 문자열로 되어있는 매트릭스를 숫자로 바꿔주었다. 종수의 아두이노는 -1, 빈칸은 0, 미친 아디우노는 1로 하였다. 미친 아두이노가 이동할 때 모든 아두이노가 이동한 후에 같은 칸에 있는지 여부를 확인해야 했기에 new_mtr을 선언해준 후 차례대로 탐색해준 후 new_mtr을 확인하여 만약 new_mtr의 값이 1보다 크다면(다른 미친 아두이노가 이미 그 칸을 점령하였다)그 칸의 값에 하나를 더해주었다. 그 외로 만약 종수의 아디우노를 만났다면 flag=True해준후 탐색을 종류하고, 앞 두가지 조건이 아니라면 단순하게 이동하려는 칸을 1로 할당해주었다. 문제는 미친 아디우노의 이동을 위해 매트릭스의 모든 요소를 탐색해도 될까였는데, 시간복잡도를 계산해보니까 최악의 경우 1000만이기 때문에 1초에 2천만의 연산을 감당할 수 있는 파이썬으로는 충분할거라 생각되어 제출해보니까 정답 처리되었다.

import sys
input = lambda: sys.stdin.readline().rstrip()
r, c = map(int, input().split())
mtr = [list(input()) for _ in range(r)]
op = input()
dx = [1, 1, 1, 0, 0, 0, -1, -1, -1]
dy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
jong = []
for i in range(r):
    for j in range(c):
        if mtr[i][j] == 'I':
            jong = [i, j]
            mtr[i][j] = -1
        elif mtr[i][j] == 'R':
            mtr[i][j] = 1
        else:
            mtr[i][j] = 0
flag = False
cnt = 0
for o in op:
    new_mtr = [[0 for _ in range(c)]for _ in range(r)]
    cnt += 1
    j_x = jong[0] + dx[int(o)-1]
    j_y = jong[1] + dy[int(o)-1]
    if mtr[j_x][j_y] == 1:
        flag = True
        break
    jong = [j_x, j_y]
    new_mtr[j_x][j_y] = -1
    for i in range(r):
        for j in range(c):
            if mtr[i][j] == 1:
                min_index  = -1
                min_val = 10000
                for k in range(9):
                    if k == 4:
                        continue
                    if min_val > abs(jong[0]-(i+dx[k])) + abs(jong[1]-(j+dy[k])):
                        min_val = abs(jong[0]-(i+dx[k])) + abs(jong[1]-(j+dy[k]))
                        min_index = k
        #print(cr[0], cr[1], min_index)
                if new_mtr[i+dx[min_index]][j+dy[min_index]] >= 1:
                    new_mtr[i+dx[min_index]][j+dy[min_index]]  += 1
                    continue
                elif new_mtr[i+dx[min_index]][j+dy[min_index]]  == -1:
                    flag = True
                    break
                else:
                    new_mtr[i+dx[min_index]][j+dy[min_index]]  = 1
        if flag:
            break
    for i in range(r):
        for j in range(c):
            if new_mtr[i][j] > 1:
                mtr[i][j] = 0
            else:
                mtr[i][j] = new_mtr[i][j]
    #         print(new_mtr[i][j], end = '')
    #     print()
    # print()
    if flag:
        break
if flag:
    print("kraj", cnt)
else:
    for i in range(r):
        for j in range(c):
            if mtr[i][j] == 0:
                print('.', end = '')
            elif mtr[i][j] == -1:
                print('I', end ='')
            else:
                print("R", end = '')
        print()