[알고리즘][Python] 백준 17837 새로운 게임 2 문제 풀이

문제 출처 : www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

---

문제 해석 : 체스말이 4개이상 모이거나 1000번을 해도 4개가 모이지 않으면 게임이 끝난다 이때 끝날 때 까지의 시간을 구하는 문제이다. (주어진 조건을 모두 충족하면서)

 

문제 풀이 : 문제에는 주어지는 조건이 있다. 체스판에 경우에 따라서 모든 경우를 차근차근 생각해서 풀이하면 된다. 

 

풀이 시간 (기록용) : 1시간 32분

 

---

풀이 코드

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


def move(now_num):
    global horse

    now_x, now_y, now_d = horse[now_num]

    nx, ny, nd = now_x + dx[now_d], now_y + dy[now_d], now_d
    if nx < 0 or nx >= N or ny < 0 or ny >= N or chess_map[nx][ny] == 2:
        if 0 <= nd <= 1:
            nd = (nd + 1) % 2
        else:
            nd = (nd - 1) % 2 + 2
        nx, ny = now_x + dx[nd], now_y + dy[nd]
        horse[now_num][2] = nd

        if not (0 <= nx < N) or not (0 <= ny < N) or chess_map[nx][ny] == 2:
            return False

    if chess_map[nx][ny] == 0:
        index = chess_map_horse[now_x][now_y].index(now_num)
        new_arr = chess_map_horse[now_x][now_y][index:]

        chess_map_horse[nx][ny] += new_arr

        if new_arr:
            for child in new_arr:
                horse[child][0], horse[child][1] = nx, ny

        chess_map_horse[now_x][now_y] = chess_map_horse[now_x][now_y][:index]
        horse[now_num] = [nx, ny, nd]

    elif chess_map[nx][ny] == 1:
        index = chess_map_horse[now_x][now_y].index(now_num)
        new_arr = chess_map_horse[now_x][now_y][index:]
        chess_map_horse[nx][ny] += new_arr[::-1]

        if new_arr:
            for child in new_arr:
                horse[child][0], horse[child][1] = nx, ny

        chess_map_horse[now_x][now_y] = chess_map_horse[now_x][now_y][:index]
        horse[now_num] = [nx, ny, nd]

    return check_end()


def check_end():
    for i in range(N):
        for j in range(N):
            if len(chess_map_horse[i][j]) >= 4:
                return True
    return False


N, K = map(int, input().split())

chess_map = [list(map(int, input().split())) for _ in range(N)]
chess_map_horse = [[[] for _ in range(N)] for _ in range(N)]
horse = []
for i in range(K):
    x, y, d = map(int, input().split())
    horse.append([x - 1, y - 1, d - 1])
    chess_map_horse[x - 1][y - 1].append(i)

time = 0
flag = False
while True:

    if time > 1000:
        time = -1
        break
    if flag is True:
        break
    time += 1
    for i in range(K):
        if move(i):
            flag = True
            break

print(time)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.