17837번 - 새로운 게임 2

문제

17837번: 새로운 게임 2 (acmicpc.net)

17837번: 새로운 게임 2

풀이 1

전체 보드의 크기는 최대 12^2 = 144인 반면, 주어지는 말의 개수는 최대 10개밖에 안된다. 따라서 이 문제의 경우, 주어진 제한조건에 따라 말의 데이터를 따로 배열에 넣어놓고 탐색하는 방법이 유효하다고 판단 가능하다.

 

문제에서 조건으로 생각해야하는 것은 보드 경계와 각 칸의 색깔이다. 조건에 의해 보드 경계 바깥으로 나가는 경우와 파란색 칸으로 가는 경우는 동일하게 취급되며, 앞 뒤 모두 이 경우가 된다면 말은 움직이지 않고 그 자리에 있게 된다.

흰색과 빨간색 칸은 원소가 들어가는 순서만 다르다.

프로그램이 종료되는 조건은 두 가지로, 턴이 1000을 넘어가는 경우와, 말을 움직이던 중간에 특정 칸에 말이 동시에 4개 이상 존재하게 되는 경우이다. 따라서 하나의 말을 움직일 때 마다 움직인 칸에 존재하는 말의 개수를 구해 4 이상이 되는지 확인해야한다.

# 동 서 북 남
dRow = [0,0,0,-1,1]
dCol = [0,1,-1,0,0]

N,K = map(int,input().split())
# 0 : 흰색, 1 : 빨간색, 2 : 파란색
color_board = [[9]*(N+1)]
for _ in range(N):
    color_board.append([9]+list(map(int,input().split())))
board = [[[] for _ in range(N+1)] for _ in range(N+1)]
pieces = [0]
for i in range(1,K+1):
    r,c,d = map(int,input().split())
    board[r][c].append(i)
    pieces.append([r,c,d])

answer = 0

flag = False
while not flag:
    answer += 1
    if answer >= 1000:
        answer = -1
        break
    for idx in range(1,K+1):
        row,col,dir = pieces[idx]
        nRow,nCol = row+dRow[dir],col+dCol[dir]
        # 다음칸이 벽이거나, 파란색일때
        if not (1 <= nRow < N+1 and 1 <= nCol < N+1) or color_board[nRow][nCol] == 2:
            if dir == 1:
                dir = 2
            elif dir == 2:
                dir = 1
            elif dir == 3:
                dir = 4
            elif dir == 4:
                dir = 3
            nRow, nCol = row + dRow[dir], col + dCol[dir]
        pieces[idx][2] = dir

        if not (1 <= nRow < N + 1 and 1 <= nCol < N + 1) or color_board[nRow][nCol] == 2:
            continue

        li = []
        li.append(board[row][col].pop())
        while li[-1] != idx:
            li.append(board[row][col].pop())

        if color_board[nRow][nCol] == 0:
            for i in range(len(li)-1,-1,-1):
                board[nRow][nCol].append(li[i])
                pieces[li[i]][0],pieces[li[i]][1] = nRow,nCol

        elif color_board[nRow][nCol] == 1:
            for i in range(len(li)):
                board[nRow][nCol].append(li[i])
                pieces[li[i]][0],pieces[li[i]][1] = nRow,nCol

        if len(board[nRow][nCol]) >= 4:
            flag = True
            break

print(answer)

풀이 2

한가지 교훈을 얻었는데, 웬만하면 구현문제는 구현으로 접근하자는 것이다. 당연한말 같지만, 연결리스트로 접근하려다가 상당한 시간을 날렸다... 시험 당일에도 새로운 방법보단 쌩 구현으로 접근하는편이 맞을것이다.

문제 자체는 매우 간단한 구조이므로, 설명은 생략한다.

# 동 서 북 남
dRow = [0,0,0,-1,1]
dCol = [0,1,-1,0,0]

N,K = map(int,input().split())
# 0:W 1:R 2:B
map_board = [[2] * (N + 2)]
for _ in range(N):
    map_board.append([2] + list(map(int, input().split())) + [2])
map_board.append([2] * (N + 2))
locs = []
dirs = []
# 좌표에 놓여있는 말들 중 가장 위에 있는 말을 가리킴
loc_board = [[[] for col in range(N+2)] for row in range(N+2)]
for k in range(K):
    r,c,d = map(int,input().split())
    locs.append([r,c])
    dirs.append(d)
    loc_board[r][c].append(k)

answer = 0
flag = False
for _ in range(1000):
    answer += 1
    for k in range(K):
        # 이동위치 확인
        row,col = locs[k]
        dir = dirs[k]
        nRow,nCol = row+dRow[dir],col+dCol[dir]
        if map_board[nRow][nCol] == 2:
            if dir == 1: dir = 2
            elif dir == 2: dir = 1
            elif dir == 3: dir = 4
            else: dir = 3
            nRow, nCol = row + dRow[dir], col + dCol[dir]
            dirs[k] = dir
        if map_board[nRow][nCol] == 2:
            continue
        # 이동
        stack = []
        while loc_board[row][col]:
            idx = loc_board[row][col].pop()
            locs[idx][0],locs[idx][1] = nRow,nCol
            stack.append(idx)
            if idx == k:
                break
        # 하얀칸
        if map_board[nRow][nCol] == 0:
            loc_board[nRow][nCol] += stack[::-1]
        # 빨간칸
        else:
            loc_board[nRow][nCol] += stack

        if len(loc_board[nRow][nCol]) >= 4:
            flag = True
            break
    if flag:
        print(answer)
        break
else:
    print(-1)