[백준] 17837번 새로운 게임 2 _ 문제 풀이

 


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 자세한 풀이 설명은 아래에 주석으로 남겼습니다. Python의 배열을 이용하여 말들을 쌓았습니다.

참고사항으로는 아래와 같습니다.

  • https://www.acmicpc.net/board/view/49492 에서 디버깅에 대한 정보를 얻을 수 있었습니다. 해당 배열의 값과 다르면 확인해보세요
  • https://hose0728.tistory.com/41 에서 숏코딩을 확인해보세요.
  • 말들을 모두 살펴보아야되는데, 해당 과정을 거치지 않고 index 실수한 채로 시간을 많이 허비했습니다. index를 항상 신경쓰세요.
WHITE, RED, BLUE = 0, 1, 2
# 우, 좌, 상, 하
RIGHT, LEFT, UP, DOWN = 1, 2, 3, 4
COLOR = ['WHITE', 'RED', 'BLUE']
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]

N, K = map(int, input().split())
# 체스판 정보
chess_map = [list(map(int, input().split())) for _ in range(N)]
# 말들을 쌓는 Stack
map_stack = [[[] for __ in range(N)] for _ in range(N)]
# 말의 좌표와 방향 받기
horse_cord = [list(map(int, input().split())) for _ in range(K)]
# 좌표는 0부터 시작하게 갱신
horse_cord = [[one_horse[0]-1, one_horse[1]-1, one_horse[2]] for one_horse in horse_cord]

# 초기 stack 갱신
for i, one_horse in enumerate(horse_cord):
    row, col = one_horse[0], one_horse[1]
    map_stack[row][col].append(i+1)

turn = 1
is_end = False
while turn < 1000 and is_end == False:
    for one_horse in range(1, len(horse_cord)+1):
        if is_end:
            break
        row, col, way = horse_cord[one_horse-1]
        next_row, next_col = row + dr[way-1], col + dc[way-1]

        # 먼저 지금 위치에 있는 말과 그 위에 있는 말들 확인
        stack_idx = False
        for i, x in enumerate(map_stack[row][col]):
            if x == one_horse:
                stack_idx = i
                break

        # 다음 위치가 out of map 이나 BLUE면 방향 변경하고 다시 다음 블록 살피기
        if next_row < 0 or next_row >= N or next_col < 0 or next_col >= N or chess_map[next_row][next_col] == BLUE:
            # 방향 변경
            if way == 1:
                next_way = 2
            elif way == 2:
                next_way = 1
            elif way == 3:
                next_way = 4
            elif way == 4:
                next_way = 3
            horse_cord[one_horse-1] = [row, col, next_way]

        row, col, way = horse_cord[one_horse-1]
        next_row, next_col = row + dr[way-1], col + dc[way-1]
        if next_row < 0 or next_row >= N or next_col < 0 or next_col >= N or chess_map[next_row][next_col] == BLUE:
            pass

        # White == 해당 위치에 있는 얘들 위에 있는거 한번에 이동
        elif chess_map[next_row][next_col] == WHITE:
            # 갈 수 있으면 갱신
            next_way = way
            horse_cord[one_horse - 1] = [next_row, next_col, next_way]
            map_stack[next_row][next_col].extend(map_stack[row][col][stack_idx:])
            for h_idx in map_stack[row][col][stack_idx + 1:]:
                horse_cord[h_idx - 1] = [next_row, next_col, horse_cord[h_idx - 1][2]]
            map_stack[row][col] = map_stack[row][col][:stack_idx]

        # RED == 이 위치로 이동한 얘들 전부 순서 변경
        elif chess_map[next_row][next_col] == RED:
            # 갈 수 있으면 갱신
            next_way = way
            horse_cord[one_horse - 1] = [next_row, next_col, next_way]
            map_stack[next_row][next_col].extend(reversed(map_stack[row][col][stack_idx:]))
            for h_idx in map_stack[row][col][stack_idx + 1:]:
                horse_cord[h_idx - 1] = [next_row, next_col, horse_cord[h_idx - 1][2]]
            map_stack[row][col] = map_stack[row][col][:stack_idx]
            
        for r in range(N):
            if is_end:
                break
            for c in range(N):
                if len(map_stack[r][c]) >= 4:
                    print(turn)
                    is_end = True
                    break
    turn += 1

if is_end == False:
    print(-1)