[BOJ/백준] 8972 미친 아두이노 파이썬

문제 링크 : https://www.acmicpc.net/problem/8972

8972번: 미친 아두이노

 

별다른 어려운 조건이나 규칙이 없어서 주어진 조건대로 구현만 하면 된다.

 

우선 종수의 위치를 따로 저장하고., 미친 아두이노의 위치는 큐에 담는다.

그리고 맵을 조금 변경했다.

빈칸은 0, 종수는 -1, 미친 아두이노는 1로 초기화를 시작하고 했다.

1 이상의 숫자는 해당 점에 미친 아두이노의 개수를 나타낸다.

 

알고리즘의 순서는 다음과 같다.

1. 종수 이동

   만약 미친 아두이노랑 만난다면 종료

 

2. 미친 아두이노 이동

  현재 큐의 길이 만큼 반복문 수행

  아두이노 위치 이동

  만약 종수랑 만난다면 종료

  이전 칸이 개수 -1, 이동한 칸의 개수 +1

 

3. 전체 미친 아두이노 체크

  아두이노 큐 돌면서 체크

  만약 현재 아두이노 칸의 개수가 1이상이면 현재 위치 저장

  만약 그렇지 않다면 다시 큐에 push

 

  저장한 위치 돌면서 맵의 값 0으로 초기화

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [1,1,1,0,0,0,-1,-1,-1]
dy = [-1,0,1,-1,0,1,-1,0,1]

board = []
q = deque()
r,c = map(int, input().split())
mx=my=0
for x in range(r):
    board.append(list(input().strip()))
    for y in range(c):
        if board[x][y] == '.':
            board[x][y] = 0
        elif board[x][y] == 'I':
            board[x][y] = -1
            mx,my=x,y
        else:
            board[x][y] = 1
            q.appendleft((x,y))
orders = list(map(int, input().strip()))
def solv():
    global board
    for cnt in range(len(orders)):
        order = orders[cnt]-1
        if not move_my(order):
            print('kraj %d'%(cnt+1))
            return

        if not move_mad():
            print('kraj %d'%(cnt+1))
            return

    for x in range(r):
        for y in range(c):
            if board[x][y] == 0:
                print('.',end='')
            elif board[x][y] == -1:
                print('I', end='')
            else:
                print('R',end='')
        print()
def move_my(order):
    global board,mx,my
    board[mx][my] = 0
    mx += dx[order]
    my += dy[order]
    if board[mx][my] > 0:
        return False
    board[mx][my] = -1
    return True

def move_mad():
    global q,board
    q_len = len(q)
    for _ in range(q_len):
        x,y = q.pop()
        nxt_location = (9875643210, 0, 0)
        for d in range(9):
            nx = x + dx[d]
            ny = y + dy[d]
            if point_validator(nx, ny):
                dist = abs(nx - mx) + abs(ny - my)
                if nxt_location[0] > dist:
                    nxt_location = (dist, nx, ny)
        nx,ny = nxt_location[1:]
        if board[nx][ny] == -1:
            return False
        board[x][y] -= 1
        board[nx][ny] += 1
        q.appendleft((nx,ny))
    renew_mad()
    return True

def renew_mad():
    global q,board
    q_len = len(q)
    destory_arduino = []
    for _ in range(q_len):
        x,y = q.pop()
        if board[x][y] > 1:
            destory_arduino.append((x,y))
        else:
            q.appendleft((x,y))
    for x,y in destory_arduino:
        board[x][y] = 0
def point_validator(x,y):
    if x < 0 or y < 0 or x >= r or y >= c:
        return False
    return True
solv()