📌 문제 : 백준 17837번
📌 문제 탐색하기
N : 체스판의 크기 ()
K : 말의 개수 ()
chess_info : 체스판의 정보
horse_info : 말의 정보
문제 풀이
크기가 N×N인 체스판에서 K개의 말로 게임을 진행했을 때 게임이 종료되는 턴의 번호를 출력하는 문제이다.
⭐️ 게임 방법
- 체스판 위에 말 K개 놓고 시작
- 이동 방향 미리 정해져 있음
- 4가지 중 하나 (위, 아래, 왼쪽, 오른쪽)
- 체스판 정보
- 칸의 색 의미 : 0은 흰색, 1은 빨간색, 2는 파란색
- 흰색 → 이동하는 칸에 말이 이미 있으면 맨 위에 놓기
- 빨간색 → 모든 말의 쌓인 순서 반대로 바꿈
- 파란색 → 이동하는 말의 이동 방향 반대로하고 한 칸 이동, 이동하려는 칸이 파란색이면 이동 ❌
- 체스판 벗어나는 경우 = 파란색과 같은 경우
- 말 정보 (3개의 정수)
- 행 번호 : 1부터 시작
- 열 번호 : 1부터 시작
- 이동 방향 : 1은 →, 2는 ←, 3은 ↑, 4는 ↓
- 턴 1번
- 1~K번 말 모두 순서대로 이동시키기
- 한 말 이동 시 위의 말도 함께 이동
- 게임 종료
- 턴 진행 중 말이 4개 쌓이는 순간 종료
- 출력
- 게임 종료되는 턴 번호
- 번호가 1000보다 크거나 절대 종료 안되면
-1
→ 과정이 매우 복잡하므로 말을 움직이는 함수를 따로 구현한다.
말 정보 입력받기
- 행, 열, 말 번호 모두 1부터 시작하는데 지도에서 접근할 땐 0부터 시작
- 입력 받은 3가지 정보에서 1을 뺀 숫자를 저장
- 체스판 위 말의 위치에 말 인덱스로 값 넣기
말 이동 함수
- 말의 위치, 이동 정보 가져오기
- 말 이동
- 4가지 방향에 대해 이동
- 범위 밖이거나 파란색이면 이동 방향 반대 & 한 칸 이동
- 방향 전환 업데이트
- 다음 위치로 이동해 동일 상황 확인
- 방향 전환 업데이트
- 함께 이동할 말 고려
- 동일 위치에 있는 말 모두 가져와서 리스트에 저장
- 색 별로 움직임 로직 작성
- 흰색 : 말 추가
- 빨간색 : 쌓인 순서 반대
- 파란색 & 범위 밖 : 방향 전환 후 위치 업데이트 & 다음 칸 확인
말 이동하며 턴 수 세기
- 턴 수가 1000이 넘을 때까지 반복해 함수 수행
- 쌓인 말의 수가 4개 이상이면 턴 수 출력 후 종료
가능한 시간복잡도
체스판 입력 →
턴 수 1000번까지 K개의 말 이동하며 함수 수행 →
최종 시간복잡도
로,최악의 경우 이 되어 제한 시간 0.5초 내에 연산이 가능하다.
알고리즘 선택
1000번 반복하면서 함수 수행
📌 코드 설계하기
- N, K 입력
- 체스판 정보 입력
- 체스판 말 위치 저장
- 말의 정보 입력
- 말 이동 함수 구현
- 결과 출력
📌 시도 회차 수정 사항
1회차
# 말의 정보 입력
horse_info = []
...
for i in range(K):
...
# 수정 전
horse_info[i] = [row-1, col-1, dir-1]
# 수정 후
horse_info.append([row-1, col-1, dir-1])- IndexError가 발생했다.
- 처음에 말 정보를 저장하는 리스트를 빈 리스트로 정의했는데 비어있는 상태에서 값을 가져오도록 코드를 작성하는 바람에 발생한 오류였다.
- 입력된 정보를 추가하는 방식으로 변경했다.
2회차
- 이동 방향을 반대로 바꾸는 수식에 오류가 있었다,
dir = (dir + 2) % 4라는 수식을 먼저 썼는데 항상 옳은 값을 반환하지 않았다.dir = (dir + 1) % 2 + (dir // 2) * 2로 수정했다.
📌 정답 코드
import sys
input = sys.stdin.readline
# N, K 입력
N, K = map(int, input().split())
# 체스판 정보 입력
chess_info = [list(map(int, input().split())) for _ in range(N)]
# 체스판 말 위치 저장
horse_loc = [[[] for _ in range(N)] for _ in range(N)]
# 말의 정보 입력
horse_info = []
for i in range(K):
row, col, dir = map(int, input().split())
# 리스트에 추가
horse_info.append([row-1, col-1, dir-1])
# 체스판에 말 위치 저장
horse_loc[row-1][col-1].append(i)
# 4가지 이동 방향 정의 (0 : 오른쪽, 1 : 왼쪽, 2 : 위, 3 : 아래)
moves = [(0, 1), (0, -1), (-1, 0), (1, 0)]
# 말 이동 함수 구현
def move_horse(i):
x, y, dir = horse_info[i]
# 이동
nx, ny = x + moves[dir][0], y + moves[dir][1]
# 범위 밖이거나 파란색인지 확인
if not (0 <= nx < N and 0 <= ny < N) or chess_info[nx][ny] == 2:
# 방향 전환 후 업데이트
dir = (dir + 1) % 2 + (dir // 2) * 2 # 방향 반대로
horse_info[i][2] = dir
# 다음 한칸 진행
nx, ny = x + moves[dir][0], y + moves[dir][1]
# 다시 확인
if not (0 <= nx < N and 0 <= ny < N) or chess_info[nx][ny] == 2:
return 0
# 같은 곳에 있는 말 모두 꺼내기
idx = horse_loc[x][y].index(i) # 이동할 말 인덱스 뽑아서
move_together = horse_loc[x][y][idx:] # 말이 이동할 때 위에 있는 말들도 같이 이동
horse_loc[x][y] = horse_loc[x][y][:idx]
# 흰색이면 말 추가
if chess_info[nx][ny] == 0:
horse_loc[nx][ny].extend(move_together)
# 빨간색일 경우 쌓인 순서 반대
if chess_info[nx][ny] == 1:
horse_loc[nx][ny].extend(move_together[::-1])
# 말 위치 업데이트
for h in move_together:
horse_info[h][0] = nx
horse_info[h][1] = ny
# 쌓인 말 4개면 종료
if len(horse_loc[nx][ny]) >= 4:
return 1
return 0
# 결과 출력
turn = 1
while turn <= 1000:
for i in range(K):
flag = move_horse(i)
if flag:
print(turn)
sys.exit()
turn += 1
print(-1)
- 결과
