8972번: 미친 아두이노 (구현)

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

8972번: 미친 아두이노

단순(?! 조금은 깐깐한) 구현 문제이다. 문제에서 제시된 게임 순서대로 꼼곰히 구현을 하면 된다. 다만 게임을 종료시키거나 로봇을 제거하는 부분을 어떻게 구현할지 적절한 아이디어를 떠올리는 것이 중요하다. 이번 글에는 내가 풀기 위해 떠올린 2개의 아이디어를 설명하고자 한다. 각 아이디어를 보면서 속으로 아이디어의 구현 가능성/명확성/타당성을 확인해보자. 참고로 1번 아이디어는 구현할 때 생각할 점이 많아 힘들었으며, 2번 아이디어는 1번 아이디어를 구현하면서 불편했던 점을 극복했다. 현재 상태와 다음 상태를 지속적으로 업데이트 할 때 현재 테이블에 계속해서 업데이트를 하는 것보다 다른 보조 테이블을 이용해 현재 테이블과 비교하면서 코딩하는 방식이 구현상 편했다. 

 

 

두가지 아이디어를 떠올려서 각각 구현을 시도하고 결국 둘 다 맞았다. 1번 아이디어는 구현이 빡세고 고려할 점이 많아 코딩하면서 계속 그려가고 테스트 케이스를 만들면서 구현했고, 2번 아이디어는 1번 아이디어와 원하는 바는 동일하나 보조 테이블을 도입해 좀 편하게 코딩 할 수 있었다.  

 

  

첫번째 아이디어는 입력받은 테이블을 기준으로 생각했고, 미친로봇들의 좌표를 저장하는 리스트를 따로 만들어 활용하고자 했다.

 

1. 종수 턴에서는 테이블에서 이동시킬 장소에 'R' 이 있으면 게임을 종료시키고, '.'라면 'I'로 채운다. 
2. 이후 미친 로봇들의 턴에서는 움직이려고 하는 미친 로봇의 원래 좌표 (x1,y1)을 리스트에서 받아온다
3. 이동시킬 좌표 (x2,y2)를 구해서 테이블에서 (x2,y2) 위치에 'I' 가 있으면 게임을 종료시킨다.
4. '.' 이 있다면 (x2,y2)를 'R' 로 바꾸고 해당 미친 로봇의 좌표 (x2,y2)를 리스트에 다시 저장한다. 
5. 'R' 이 있다면 이동하려고자 하는 좌표에 미친 로봇이 있다는 의미인데 이 미친 로봇이 이번 턴에 움직여서 해당 위치에 있는 것인지, 아니면 아직 움직이지 않았는데 해당 위치에 있는 것인지 확인을 해야한다. 실제 이를 구현하기 어려워서 6,7을 도입했다.
6. (x2,y2) 위치에 'R'이 존재하면 이동할 때 R을 붙여 'RR'로 만든다 (만약 (x2,y2) 위치에 'RR...R(R이 n개)' 이 있으면 R을 하나 추가시켜 n+1개의 R을 만든다.) 이에 의하면 현재 (x1,y1)은 테이블에서 'R' 이거나 'RR...' 이므로 (x2,y2)로 움직일 때 (x1,y1)의 R을 하나 제거하거나(R이 2개이상 있었을 때)  '.'(R이 1개있었을 때) 으로 만든다. 
7. 이때 테이블에서 RR..꼴로 존재하는 것은 이동을 했음에도 불구하고 겹치는 경우로 보아 '.'으로 고치고 다시 종수 턴으로 넘긴다. 

table = []
r,c = map(int,input().split())
for i in range(r):
    table.append(list(map(str,input())))
route = input()

def solve(table, r, c, route):
    dx = [1,1,1,0,0,0,-1,-1,-1]
    dy = [-1,0,1,-1,0,1,-1,0,1]
    for i in range(len(route)):
        mad_robots = []
        nx, ny = 0, 0
        for k in range(r):
            for j in range(c):
                if table[k][j] == 'I':
                    nx, ny = k, j
                if table[k][j] == 'R':
                    mad_robots.append([k, j])
        table[nx][ny] = '.'
        nx += dx[int(route[i])-1]
        ny += dy[int(route[i])-1]
        if table[nx][ny] == 'R':
            return i+1
        table[nx][ny] = 'I'
        for j in range(len(mad_robots)):
            x1,y1 = mad_robots[j]
            dis = []
            for k in range(9):
                mx = x1 + dx[k]
                my = y1 + dy[k]
                dis.append(abs(nx-mx)+abs(ny-my))
            direction = dis.index(min(dis))
            x2 = x1 + dx[direction]
            y2 = y1 + dy[direction]
            if table[x1][y1] == 'R':
                table[x1][y1] = '.'
                if table[x2][y2] == 'I':
                    return i+1
                elif table[x2][y2] == '.':
                    table[x2][y2] = 'R'
                elif 'R' in table[x2][y2]:
                    table[x2][y2] = 'R' * (len(table[x2][y2]) + 1)
            elif table[x1][y1] != '.':
                table[x1][y1] = 'R' * (len(table[x1][y1]) - 1)
                if table[x2][y2] == 'I':
                    return i+1
                elif table[x2][y2] == '.':
                    table[x2][y2] = 'R'
                elif 'R' in table[x2][y2]:
                    table[x2][y2] = 'R' * (len(table[x2][y2]) + 1)
        for j in range(r):
            for k in range(c):
                if len(table[j][k]) >= 2:
                    table[j][k] = '.'
    return table

s = solve(table,r,c,route)
if type(s) == type(0):
    print('kraj {0}'.format(s))
else:
    for i in s:
        line = ''
        for j in i:
            line += str(j)
        print(line)

두번째 아이디어는 첫번째 아이디어와 비슷하나, 첫번째 아이디어에서 현재 위치를 저장하는 테이블을 하나만 사용해 미친 로봇이 이번 턴에 움직여서 해당 위치에 있는 것인지, 아니면 아직 움직이지 않았는데 해당 위치에 있는 것인지 확인하기 힘들었다. 따라서 현재 위치를 저장하는 테이블과 다음 위치를 저장하는 보조테이블을 이용하였다.

 

1. 종수 턴을 시작할 때 '.' 로 초기화된 원래 테이블과 크기가 같은 보조 테이블을 만든다. 
2. 종수 턴에서는 테이블에서 로봇을 이동시킬 장소에 'R' 이 있으면 게임을 종료시키고, '.'라면 보조 테이블에 'I'를 채운다.
3. 미친 로봇들 턴에서는 미친 로봇을 이동시킬 장소 (x,y)에서 보조 테이블 값이 'I' 면 게임을 종료시키고, '.' 이면 보조테이블에 'R'을 채우고, 'R' 이면 이미 (x,y) 에 이동한 로봇이 있다는 것으로 'X'를 채운다. 
4. 미친 로봇들 턴이 끝나고 보조테이블에서 'X'를 '.' 로 바꾸고 복사해서 원래 테이블에 대입해 다시 종수 턴으로 넘긴다.  

 

table = []
r,c = map(int,input().split())
for i in range(r):
    table.append(list(map(str,input())))
route = input()

def solve(table,r,c,route):
    dx = [1,1,1,0,0,0,-1,-1,-1]
    dy = [-1,0,1,-1,0,1,-1,0,1]
    nx,ny = 0,0
    for i in range(r):
        for j in range(c):
            if table[i][j] == 'I':
                nx,ny = i,j

    for i in range(len(route)):
        auxtable = [['.' for _ in range(c)] for _ in range(r)]
        nx += dx[int(route[i])-1]
        ny += dy[int(route[i])-1]
        auxtable[nx][ny] = 'I'
        if table[nx][ny] == 'R':
            return i+1
        for j in range(r):
            for k in range(c):
                if table[j][k] == 'R':
                    dis = []
                    for m in range(9):
                        mx = j + dx[m]
                        my = k + dy[m]
                        dis.append(abs(nx-mx)+abs(ny-my))
                    direction = dis.index(min(dis))
                    x = j + dx[direction]
                    y = k + dy[direction]
                    if auxtable[x][y] == 'I':
                        return i+1
                    elif auxtable[x][y] == '.':
                        auxtable[x][y] = 'R'
                    else:
                        auxtable[x][y] = 'X'
        for j in range(r):
            for k in range(c):
                if auxtable[j][k] == 'X':
                    auxtable[j][k] = '.'
        table = auxtable.copy()
    return table

s = solve(table,r,c,route)
if type(s) == type(0):
    print('kraj {0}'.format(s))
else:
    for i in s:
        line = ''
        for j in i:
            line += str(j)
        print(line)