[백준 17837] 새로운 게임2

1. 문제

www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

2. 접근 방법

시뮬이라 하라는대로만 하면 된다. ㅠㅠ

 

턴마다 다음과 같은 과정을 거쳐야한다.

 

1. 말의 갯수 만큼 말의 순서대로 이동시킨다.

1-1. 이동하려는 칸이 흰색인경우

      if 해당 칸에 이미 말이 있는 경우

        그 위에 얹음 (ex. DE가 이미 존재하고, ABC가 오는 상황이라면 -> DEABC)

1-2. 이동하려는 칸이 빨간색인경우

      if 해당 칸에 이미 말이 있는 경우

         역으로 얹음 (ex. DE가 이미 존재하고, ABC가 오는 상황이라ㅕㅁㄴ -> DECBA)

1-3. 이동하려는 칸이 파란색이거나 체스판의 영역을 벗어나는 경우

      현재 말의 이동방향을 반대로 하고, 한 칸 이동

      주의 : 현재 말만 방향 바꿈

      if 이동방향을 반대로 했지만 이동하려는 칸이 파란색 or 체스판의 영역을 벗어나는 경우:

         이동하지 않고 stay

 

종료조건

1. 턴이 1000회를 넘어가는 경우

2. 말이 4개 이상 쌓이는 순간 게임 종료 (턴 종료 여부와 관계없이 이동 중에 한 칸에 말이 4개 이상 쌓이는 경우 종료)

3. 코드

python

def check(nx, ny):
    if len(horse_board[ny][nx]) >= 4:
        return True
    return False

def isBoard(x, y):
    if x < 0 or x >= N or y < 0 or y >= N or color_board[y][x] == 2:
        return False
    return True

def movecolor(tx, ty, move_items, type):
    global horses, horse_board
    while move_items:
        horse = move_items.pop(type)
        horse_board[ty][tx].append(horse)
        horse_idx = horse[0] - 1
        horses[horse_idx][0] = ty
        horses[horse_idx][1] = tx
def move(_i):
    global horses, horse_board
    ny, nx, nd = horses[_i]
    idx = horse_board[ny][nx].index([_i + 1, nd])
    move_items = horse_board[ny][nx][idx:]
    if check(nx, ny):
        return True
    horse_board[ny][nx] = horse_board[ny][nx][0:idx]

    tx, ty = nx + dx[nd], ny + dy[nd]

    if isBoard(tx, ty):
        if color_board[ty][tx] == 0:
            movecolor(tx, ty, move_items, 0)
        elif color_board[ty][tx] == 1:
            movecolor(tx, ty, move_items, -1)
        if check(tx, ty):
            return True
    else:
        if nd % 2:
            nd = (nd + 3) % 4
        else:
            nd = (nd + 1) % 4
        horses[_i][2] = nd
        for i in range(len(move_items)):
            if move_items[i][0] - 1 == _i:
                move_items[i][1] = nd
        tx, ty = nx + dx[nd], ny + dy[nd]
        if isBoard(tx, ty):
            if color_board[ty][tx] == 0:
                movecolor(tx, ty, move_items, 0)
            elif color_board[ty][tx] == 1:
                movecolor(tx, ty, move_items, -1)
            if check(tx, ty):
                return True
        else:
            while move_items:
                horse = move_items.pop(0)
                if horse[0] - 1 == _i:
                    horse[1] = nd
                horse_board[ny][nx].append(horse)
            if check(nx, ny):
                return True
    return False

N, K = map(int, input().split())
color_board = [list(map(int, input().split())) for _ in range(N)]
horses = [list(map(int, input().split())) for _ in range(K)]
horse_board = [[list() for _ in range(N)] for _ in range(N)]
dx, dy = (1, -1, 0, 0), (0, 0, -1, 1)
for i in range(1, K + 1):
    y, x, dir = horses[i - 1]
    horse_board[y - 1][x - 1].append([i, dir - 1])
    horses[i - 1] = [y - 1, x - 1, dir - 1]
ans = 1
isAns = False
while not isAns:
    if ans > 1000:
        break
    for i in range(K):
        isAns = move(i)
        if isAns:
            break
    if not isAns:
        ans += 1
if isAns:
    print(ans)
else:
    print(-1)

4. 마치며

오타가 너무 많아서 ㅠ ㅠ ㅠ ㅠ ㅠ 정말 많은 디버깅을 했다 후 ....

 

디버깅용 코드

def check(nx, ny):
    print(len(horse_board[ny][nx]), '갯수')
    if len(horse_board[ny][nx]) >= 4:
        return True
    return False

def isBoard(x, y):
    if x < 0 or x >= N or y < 0 or y >= N or color_board[y][x] == 2:
        return False
    return True

def movewhite(tx, ty, move_items):
    global horses, horse_board
    while move_items:
        horse = move_items.pop(0)
        horse_board[ty][tx].append(horse)
        horse_idx = horse[0] - 1
        horses[horse_idx][0] = ty
        horses[horse_idx][1] = tx

def movered(tx, ty, move_items):
    global horses, horse_board
    while move_items:
        horse = move_items.pop()
        horse_board[ty][tx].append(horse)
        horse_idx = horse[0] - 1
        horses[horse_idx][0] = ty
        horses[horse_idx][1] = tx

def move(_i):
    print(_i+1, '말 진행중')
    global horses, horse_board
    ny, nx, nd = horses[_i]
    # 현재 칸에서 몇번 째에 위치하고 있는지 확인
    idx = horse_board[ny][nx].index([_i+1, nd])
    move_items = horse_board[ny][nx][idx:]
    if check(nx, ny):
        return True
    # if _i+1 ==3 or _i+1 ==4:
        # print(horse_board[ny][nx], nx, ny , len(horse_board[ny][nx], '여기가 움직일 곳')
    horse_board[ny][nx] = horse_board[ny][nx][0:idx]

    tx, ty = nx + dx[nd], ny + dy[nd]

    if isBoard(tx, ty):
        # 흰색으로 이동할 경우
        if color_board[ty][tx] == 0:
            movewhite(tx, ty, move_items)

        # 빨간색으로 이동할 경우
        elif color_board[ty][tx] == 1:
            movered(tx, ty, move_items)

        if check(tx, ty):
            return True

    else:
        if nd % 2:
            nd = (nd+3)%4
        else:
            nd = (nd+1)%4
        # 파란색 만났을 때 방향 바꿔주기
        horses[_i][2] = nd
        for i in range(len(move_items)):
            if move_items[i][0]-1 == _i:
                move_items[i][1] = nd
        tx, ty = nx + dx[nd], ny + dy[nd]
        if isBoard(tx, ty):
            if color_board[ty][tx] == 0:
                movewhite(tx, ty, move_items)
            elif color_board[ty][tx] == 1:
                movered(tx, ty, move_items)
            if check(tx, ty):
                return True
        else:
            while move_items:
                horse= move_items.pop(0)
                if horse[0]-1 == _i:
                    horse[1] = nd
                horse_board[ny][nx].append(horse)
            if check(nx, ny):
                return True
    return False

N, K = map(int, input().split())
# 0은 흰색, 1은 빨간색, 2는 파란색
color_board = [list(map(int, input().split())) for _ in range(N)]
horses = [list(map(int, input().split())) for _ in range(K)]
horse_board = [[list() for _ in range(N)] for _ in range(N)]
dx, dy = (1, -1, 0, 0), (0, 0, -1, 1)
# dir정보: 0 오른쪽 1 왼쪽 2 위쪽 3 아래쪽
for i in range(1, K+1):
    y, x, dir = horses[i-1]
    # 말의 인덱스, 방향 정보 담음
    horse_board[y-1][x-1].append([i, dir-1])
    # 말의 인덱스, 방향을 0부터로 바꾸ㅓ줌
    horses[i-1] = [y-1, x-1, dir-1]

ans = 1
isAns = False

print('start')
for i in range(len(horse_board)):
    print(horse_board[i])

while not isAns:
    print(ans, '번째 턴')
    if ans > 1000:
        break

    for i in range(K):
        isAns = move(i)
        if isAns:
            print(ans, 'ans')
            break
    for i in range(len(horse_board)):
        print(horse_board[i])
    if not isAns:
        ans += 1

print('after')
for i in range(len(horse_board)):
    print(horse_board[i])

if isAns:
    print(ans)
else:
    print(-1)