[백준 8972] 미친 아두이노(Python 풀이)

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

8972번: 미친 아두이노

---

풀이

문제 조건만 잘 확인해서 구현하면 쉽게 풀리는 문제였습니다.

입력

R, C = map(int, input().split(' '))
board = [list(map(str, input())) for _ in range(R)]
moves = list(map(int, input()))

연속된 문자열 형태로 입력되기 때문에 위와 같이 map을 이용하여 list 형태로 입력받습니다.

움직이는 방향

그림에는 총 8방향이 있는 것 처럼 표현되지만, 가만히 있는 경우(5번)도 움직이는 방향에 포함됩니다. 움직이는 방향을 index를 이용하여 다음과 같이 정의합니다. 그리고 종수의 아두이노와 미친 아두이노의 위치 또한 전역변수로 저장합니다.

dy = (EMPTY, 1, 1, 1, 0, 0, 0, -1, -1, -1)
dx = (EMPTY, -1, 0, 1, -1, 0, 1, -1, 0, 1)
 
loc_jongsu = [(y, x) for y in range(R) for x in range(C) if board[y][x] == 'I'][0]
loc_ardu = [(y, x) for y in range(R) for x in range(C) if board[y][x] == 'R']
 

 

 

1. 종수 아두이노 이동

def isCrazyArduino(y, x):
    return board[y][x] == 'R'
 
 
def move_arduino(direction):
    global loc_jongsu
    y, x = loc_jongsu
    ny = y + dy[direction]
    nx = x + dx[direction]
 
    if isCrazyArduino(ny, nx):
        return False
    else:
        loc_jongsu = (ny, nx)
        board[y][x] = "."
        board[ny][nx] = "I"
        return True
 

moves 변수에 저장된 direction을 입력받아 move_arduino() 함수에서 종수의 아두이노를 이동시킵니다. 이때 isCrazyArduino() 함수는 이동 시킨 종수의 아두이노 위치에 미친 아두이노가 있는지 확인하며, 미친 아두이노가 있는 경우 False를 반환하며 게임이 끝남을 알립니다. 미친 아두이노가 없는 경우 loc_jongsu와 보드를 업데이트하고 True를 반환합니다.

2. 미친 아두이노 이동

def move_crazy_arduino():
    global loc_ardu
    man_y, man_x = loc_jongsu
    new_loc_ardu = []
    loc_count = {}
 
    for y, x in loc_ardu:
        board[y][x] = "."
        min_dist = 99999999
        min_loc = (0, 0)
        #check next location
        for d in range(1, 10, 1):
            if d == 5: continue
            ny = y + dy[d]
            nx = x + dx[d]
            if ny < 0 or nx < 0 or ny >= R or nx >= C:
                continue
            dist = abs(ny - man_y) + abs(nx - man_x)
            if min_dist > dist:
                min_dist = dist
                min_loc = (ny, nx)
 
        if min_loc == loc_jongsu: # 아두이노와 만남
            return False
        new_loc_ardu.append(min_loc) # 아두이노가 안겹치는 경우
        if min_loc in loc_count.keys():
            loc_count[min_loc] += 1
        else:
            loc_count[min_loc] = 1
 
    tmp_list = []
    for loc in new_loc_ardu:
        if loc in tmp_list or loc_count[loc] > 1:
            continue
        tmp_list.append(loc)
 
    loc_ardu = tmp_list
    for y, x in tmp_list:
        board[y][x] = "R"
    return True

이후 미친 아두이노를 8방향으로 움직이며 준수의 아두이노와 최소거리가 되는 지점으로 이동합니다. 이동후에 loc_count를 통하여 아두이노가 겹치는 부분이 있으면 아두이노가 폭파했다고 가정하여 이동후의 미친 아두이노 리스트에 포함하지 않습니다. 그리고 loc_ardu 리스트와 보드의 값을 갱신해줍니다.

전체흐름

전체흐름은 다음과 같습니다.

def solve():
    for i, d in enumerate(moves):
        if not move_arduino(d):
            print("kraj %d"%(i+1))
            exit()
        if not move_crazy_arduino():
            print("kraj %d"%(i+1))
            exit()
    pboard()

move_arduino()를 이용하여 moves에 저장된 값에 따라 아두이노를 움직이고 false를 반환하는 경우 kraj <움직인 횟수>를 출력합니다. move_crazy_arduino() 함수도 동일합니다.

 

전체 소스 코드

R, C = map(int, input().split(' '))
board = [list(map(str, input())) for _ in range(R)]
moves = list(map(int, input()))
EMPTY = -3
dy = (EMPTY, 1, 1, 1, 0, 0, 0, -1, -1, -1)
dx = (EMPTY, -1, 0, 1, -1, 0, 1, -1, 0, 1)
 
loc_jongsu = [(y, x) for y in range(R) for x in range(C) if board[y][x] == 'I'][0]
loc_ardu = [(y, x) for y in range(R) for x in range(C) if board[y][x] == 'R']
 
 
def pboard():
    for r in board:
        print("".join(r))
 
 
def isCrazyArduino(y, x):
    return board[y][x] == 'R'
 
 
def move_arduino(direction):
    global loc_jongsu
    y, x = loc_jongsu
    ny = y + dy[direction]
    nx = x + dx[direction]
 
    if isCrazyArduino(ny, nx):
        return False
    else:
        loc_jongsu = (ny, nx)
        board[y][x] = "."
        board[ny][nx] = "I"
        return True
 
 
def move_crazy_arduino():
    global loc_ardu
    man_y, man_x = loc_jongsu
    new_loc_ardu = []
    loc_count = {}
 
    for y, x in loc_ardu:
        board[y][x] = "."
        min_dist = 99999999
        min_loc = (0, 0)
        #check next location
        for d in range(1, 10, 1):
            if d == 5: continue
            ny = y + dy[d]
            nx = x + dx[d]
            if ny < 0 or nx < 0 or ny >= R or nx >= C:
                continue
            dist = abs(ny - man_y) + abs(nx - man_x)
            if min_dist > dist:
                min_dist = dist
                min_loc = (ny, nx)
 
        if min_loc == loc_jongsu: # 아두이노와 만남
            return False
        new_loc_ardu.append(min_loc) # 아두이노가 안겹치는 경우
 
        # 위치에 대한 아두이노 개수 파악
        if min_loc in loc_count.keys():
            loc_count[min_loc] += 1
        else:
            loc_count[min_loc] = 1
 
 
    tmp_list = []
    for loc in new_loc_ardu:
        # 한 위치에 아두이노 여러개가 있는 경우 폭파했다고 가정하여 아두이노 리스트에 포함하지 않음
        if 음oc in tmp_list or loc_count[loc] > 1:
            continue
        tmp_list.append(loc)
 
    loc_ardu = tmp_list
    for y, x in tmp_list:
        board[y][x] = "R"
    return True
 
 
def solve():
    for i, d in enumerate(moves):
        if not move_arduino(d):
            print("kraj %d"%(i+1))
            exit()
        if not move_crazy_arduino():
            print("kraj %d"%(i+1))
            exit()
    pboard()
 
solve()