[221005] 백준 17837 : 새로운 게임 2

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

17837번: 새로운 게임 2

1. 조건 이해를 얼마나 잘할 수 있는가?

 해당 문제는 조건이 차아아아암 어렵게 제시되어있다. 어쩌면 내 독해력이 부족한 것일 수도 있지만, 아무 생각 없이 읽으면 엥? 할 때가 싶다. 그나마 이동하는 경로에 파란색 블록 판정인 경우는 쉽게 받아들여진다.

 

흰색의 이동 조건부터 보자. 예문을 그림으로 표현하면 다음과 같다.

 

"예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다."

"D, E 가 있는 경우에는"이라는 표현이 참 애매하다 어떤 순으로 쌓여있는지는 모른다는 이야기가 될 수도 있다. 차라리 "이동하려는 칸에 D, E 순으로 블록이 쌓여있는 경우에는"이라고 표현해주는 게 더 명확할지도 모르겠다. 

 

다음은 이동하려는 칸이 빨간색일 경우이다.

움직이려는 말들의 순서를 먼저 뒤집고 쌓아주면 된다.

2. 그렇다면 어떻게 운용할 것인가?

 본 문제에서는 나는 3차원 배열을 활용했다. 각 좌표마다 타일 색상을 위한 보드판은 그대로 놔두고 3차원 배열을 새로 생성하여 문제를 풀었다. 이렇게 하면 순서대로 움직이는 말들을 제어하기 쉬워진다. 마찬가지로 흰색의 경우를 예를 들어 인덱스를 표현해서 다시 그림을 그려보면 다음과 같다.

 

 

이제 3차원 배열을 활용하여 A번 말이 움직이는 경우에 대해 생각해보자.

1. A번 말의 좌표의 리스트에서 인덱스로 위치를 찾고, 그 뒤로 떼어내서 temp에 넣는다.
2. 그리고 움직이려는 타일 종류에 따라 (흰색, 빨간색) 조건을 해결해주고 떼어낸 temp 크기만큼 좌표를 모두 갱신해준다.
3. 그리고 말이 4개 쌓여있는지 확인하고, 없는 경우에 A+1 번째 말을 움직인다.

문제에서 설명한 것처럼 1번 말이 움직인다고 했을 때 과정을 그림으로 표현하면 다음과 같다.

그리고 이를 이동하려는 다음 타일이 흰색인 경우와 빨간색인 경우에 소스코드는 다음과 같이 작성할 수 있다.

if board[nx][ny] == 0 :
    k_info[i][0], k_info[i][1] = nx, ny
    # 이 놈 위에 있는 녀석 한꺼번에 이동시키자.
    tmp = new_board[x][y][new_board[x][y].index(i): ]
    for j in range(len(tmp)):
        new_board[nx][ny].append(tmp[j])
        k_info[tmp[j]][0], k_info[tmp[j]][1] = nx, ny
    del new_board[x][y][new_board[x][y].index(i):]
    break
if board[nx][ny] == 1 :
    k_info[i][0], k_info[i][1] = nx, ny
    tmp = new_board[x][y][new_board[x][y].index(i):]
    # 반대로 뒤집자
    filp = []
    for j in range(len(tmp)-1, -1, -1):
        filp.append(tmp[j])
    for j in range(len(filp)):
        new_board[nx][ny].append(filp[j])
        k_info[filp[j]][0], k_info[filp[j]][1] = nx, ny
    del new_board[x][y][new_board[x][y].index(i):]
    break

3. 전체 코드

메모리 : 117072 KB, 시간 : 208 ms, 풀이 시간 : 90분 + a

※ a인 이유는.. 문제를 풀었는데 카페 시간이 다되어서 귀가하고 마무리해서 그렇다.. 본시험이었으면 바로 탈락.

※ 아이디어 접근은 나쁘지 않았던 것 같다.

N, K = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
k_info = [list(map(int, input().split())) for _ in range(K)]
for i in range(K):
    k_info[i][0] -= 1
    k_info[i][1] -= 1
    k_info[i][2] -= 1

new_board = [[[] for _ in range(N)] for _ in range(N)]

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def change(direction):
    if direction == 0 : direction = 1
    elif direction == 1 : direction = 0
    elif direction == 2 : direction = 3
    else : direction = 2
    return direction

def solve():
    for i, (x, y, _) in enumerate(k_info) :
        new_board[x][y].append(i)
    result = 0
    while True :
        for i in range(K) :
            blue_cnt = 0
            check = False
            x, y, d = k_info[i]
            while True :
                nx = x + dx[d]
                ny = y + dy[d]
                # 파란색 판
                if nx < 0 or nx >= N or ny < 0 or ny >= N or board[nx][ny] == 2 :
                    blue_cnt += 1
                    if blue_cnt == 2 :
                        break
                    else :
                        d = change(d)
                        k_info[i][2] = d
                        continue
                elif 0 <= nx < N and 0 <= ny < N:
                    if board[nx][ny] == 0 :
                        k_info[i][0], k_info[i][1] = nx, ny
                        # 이 놈 위에 있는 녀석 한꺼번에 이동시키자.
                        tmp = new_board[x][y][new_board[x][y].index(i): ]
                        for j in range(len(tmp)):
                            new_board[nx][ny].append(tmp[j])
                            k_info[tmp[j]][0], k_info[tmp[j]][1] = nx, ny
                        del new_board[x][y][new_board[x][y].index(i):]
                        break
                    if board[nx][ny] == 1 :
                        k_info[i][0], k_info[i][1] = nx, ny
                        tmp = new_board[x][y][new_board[x][y].index(i):]
                        # 반대로 뒤집자
                        filp = []
                        for j in range(len(tmp)-1, -1, -1):
                            filp.append(tmp[j])
                        for j in range(len(filp)):
                            new_board[nx][ny].append(filp[j])
                            k_info[filp[j]][0], k_info[filp[j]][1] = nx, ny
                        del new_board[x][y][new_board[x][y].index(i):]
                        break
            # 검사하자
            for xi in range(N):
                for yj in range(N):
                    if len(new_board[xi][yj]) >= 4 :
                        check = True
                        break
                if check == True :
                    break
            if check == True :
                break
        result += 1
        if check == True :
            break
        if result > 1000: break
    return result

time = solve()
if time > 1000 : print(-1)
else : print(time)