BOJ - 새로운 게임2 17837번 (python)

❓ 문제 - 백준 새로운 게임2 17837번 - python 풀이법

 

출처 

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

17837번: 새로운 게임 2

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• board 리스트를 통해 보드의 정보를 입력받고, horse 리스트에 말의 위치(x,y) 방향(d)의 정보를 입력받고, chess 리스트를 통해서 현재 체스판에 행과 열에 놓여져 있는 말의 번호를 저장한다.
• solve() 함수를 통해 모든 말에 대해서 이동을 수행한 후 count 1 증가 시켜주고 턴의 횟수, 즉 count가 1000번이 넘으면 게임을 강제로 종료시킨다. 또한 말을 이동하면서 solve 함수를 통해 False값이 반환되면(말이 한 체스판의 위치에서 4마리 이상 쌓아짐) count를 출력한 후 게임을 종료한다.

2. solve()

• 이동했을 때 체스판의 범위를 넘거나 칸이 파란색인 경우 동일하게 처리할 수 있도록 구현하는데, change_dir() 함수를 통해 방향을 바꿔주고 방향을 바꾼 곳으로 한 칸 더 이동했을 때 또 다시 범위를 넘거나 파란색 칸이면 말을 이동하지 않는다.
•  이동하기 전 현재위치에서 chess 리스트를 사용하여 horse_up 리스트를 통해 현재 이동하려는 말 ~ 그 위에 쌓아져있는 말에 대한 정보를 저장한다. 또한 말을 이동하기 위해서 chess 리스트에서 현재 이동하려는 말 ~ 그 위에 쌓아져있는 말에 대한 번호를 지운다.
•  만약 이동하려는 위치가 빨간색 칸이면 horse_up 리스트에 들어있는 말의 정보를 한칸씩 뒤로 움직인다.
• 이동하려는 위치 nx, ny에 horse_up 리스트로 현재 이동하려는 말 ~ 그 위에 쌓아져 있는 말의 번호를 chess판에 넣어주고, horse 리스트에 이동된 말들의 위치 정보를 변경해준다.
• 이동이 끝났을 때 만약 이동된 곳에 말이 4개 이상 쌓아져 있다면 게임을 종료할 수 있게 False를 반환한다.

 

 

💻 소스코드

n, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
chess = [[[] for _ in range(n)] for _ in range(n)]
# 동 - 서 - 북 - 남
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
horse = []

for i in range(k):
    x, y, d = map(int, input().split())
    horse.append([x-1, y-1, d-1])
    chess[x-1][y-1].append(i)

count = 0

def change_dir(d):
    if d in [0, 2]:
        d += 1
    elif d in [1, 3]:
        d -= 1
    return d

def solve(h_num):
    x, y, d = horse[h_num]
    nx = x + dx[d]
    ny = y + dy[d]
    if 0 > nx or nx >= n or 0 > ny or ny >= n or board[nx][ny] == 2:
        d = change_dir(d)
        horse[h_num][2] = d
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 > nx or nx >= n or 0 > ny or ny >= n or board[nx][ny] == 2:
            return True

    horse_up = []
    for h_idx, h_n in enumerate(chess[x][y]):
        if h_n == h_num:
            horse_up.extend(chess[x][y][h_idx:])
            chess[x][y] = chess[x][y][:h_idx]
            break

    if board[nx][ny] == 1:
        horse_up = horse_up[-1::-1]

    for h in horse_up:
        horse[h][0], horse[h][1] = nx, ny
        chess[nx][ny].append(h)

    if len(chess[nx][ny]) >= 4:
        return False
    return True

while True:
    what = False
    if count > 1000:
        print(-1)
        break
    for i in range(k):
        if solve(i) == False:
            what = True
            break
    count += 1
    if what:
        print(count)
        break