[백준_17837]새로운 게임2 with Python

백준(BOJ) "삼성 SW 역량 테스트 기출 문제" 문제집: 새로운 게임2(골드 2)

문제 출처: www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

 

1. 알고리즘

• 체스말 입력 시 순서대로 0번부터 K-1번까지 번호를 매김.
• while 반복문으로 실행된 턴 수(play_count) 확인
  • 실행된 턴 수가 1000회 초과인 경우, play_count를 -1로 갱신, while 반복문을 종료한다
    • 말 번호 순서대로 이동
      • chess_pieces에 번호 키 값의 값을 받아와 N번 말의 위치와 방향 값을 받아옴
      • 현재 움직일 말 뒤에 엎힌 말까지 이동할 말 리스트를 가져옴
        • pieces_count에 (r, c) 키 값의 리스트를 받아와 현재 이동 말의 위치를 index(N)로 확인
        • 현재 말부터 리스트 끝까지의 리스트를 move_pieces 리스트로 저장
        • 현재 말 이전의 말들만을 pieces_count[(r, c)]에 남겨둠
      • 현재 말의 이동 방향에 따라 이동할 칸(dr, dc)을 연산
      • 칸의 범위와 색을 확인하여 연산
        • 범위 안이고, 파란 색이 아님 == 하얀색/빨간색
          • 빨간색일 때 예외처리 ▶ move_pieces를 거꾸로 뒤집어줌
          • pieces_count[(dr, dc)]에 move_pieces를 더하여 말을 이동
          • chess_pieces에서 이동한 말들의 location 값을 (dr, dc)로 변경
        • 범위 밖이거나, 파란색일 때
          • change_directions 딕셔너리를 사용, 방향 전환
          • chess_pieces의 N번 말 방향 값을 갱신해줌
          • 새 방향을 사용, 이동할 칸(dr, dc)을 연산
          • 이동할 칸의 범위와 색을 확인, 연산
            • 범위 안이고, 파란 색이 아님 == 하얀색/빨간색
              
              • 위와 상동
            • 범위 밖이거나 파란색일 때
              • 이동할 좌표를 제자리(r, c)로 변경
              • pieces_count[(r, c)]에 move_pieces 추가
      • 현재 이동한 칸 이외의 칸에서는 이동이 일어나지 않음 ▶ 현재 이동한 칸의 말 갯수만 확인
        • 4개 이상이면 break_flag변수 값을 True로 변경
        • 말 이동 for문 반복문을 break로 벗어남
  • break_flag 값을 검사하여 True이면 while 반복문 종료
  • play_count 증가
• while 반복문 종료된 후, 실행된 턴 수(play_count) 출력

 

2. 유의 사항

• 턴 진행 중 한 칸에 말 4개 이상 쌓이면 종료해야함
  • 턴이 끝난 후가 아님. 말이 움직이던 중 검사 필요
• 파란색을 만나 방향을 반대로 바꿀 시, 현재 이동 말의 방향만 바뀜. 현재 말 위에 엎힌 말의 방향은 바뀌지 않음
• 파란색을 만나 반대방향으로 이동 시, 이동할 칸의 색도 고려해야함
  • 빨간색-역방향 이동, 하얀색-정방향 이동, 파란색/범위 밖-정지

 

3. 어려웠던 점, 해결 방법

 

4. 소스코드

상세 코드 설명은 주석

import sys
from collections import defaultdict
 
 
if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    chess_board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #체스말 정보 딕셔너리, 격자판의 체스말 상황 정보 딕셔너리
    chess_pieces, pieces_count = defaultdict(dict), defaultdict(list)
    for idx in range(K):
        r, c, d = map(int, sys.stdin.readline().split())
        chess_pieces[idx] = {'location': (r-1, c-1), 'direction': d-1}
        pieces_count[(r-1, c-1)].append(idx)
 
    directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    #방향 전환 용도의 딕셔너리
    change_directions = {0: 1, 1: 0, 2: 3, 3: 2}
 
    play_count = 1
    break_flag = False
    while True:
        #진행된 턴 수가 1000회 초과 시 while 반복문 종료
        if play_count > 1000:
            play_count = -1
            break
 
        #순서대로 말 이동
        for id in range(K):
            #(행 위치, 열 위치), 방향
            (r, c), d = chess_pieces[id].values()
 
            #이동할 말 리스트
            move_piece_index = pieces_count[(r, c)].index(id)
            move_pieces = pieces_count[(r, c)][move_piece_index:]
            #이동 말 아래에 쌓인 말이 있다면 그 말들만으로 갱신
            if pieces_count[(r, c)][:move_piece_index]:
                pieces_count[(r, c)] = pieces_count[(r, c)][:move_piece_index]
            #이동 말 아래에 쌓인 말이 없다면 딕셔너리에서 해당 위치 키 값 삭제
            else:
                pieces_count.pop((r, c))
 
            #이동할 위치
            dr = r + directions[d][0]
            dc = c + directions[d][1]
            #범위 내부이고, 파란색이 아닐 때
            if (0 <= dr < N and 0 <= dc < N) and chess_board[dr][dc] != 2:
                #빨간색일 때 move_pieces 뒤집기
                if chess_board[dr][dc] == 1:
                    move_pieces = move_pieces[::-1]
 
                #말 이동
                pieces_count[(dr, dc)].extend(move_pieces)
                for mp in move_pieces:
                    chess_pieces[mp]['location'] = (dr, dc)
            #범위 밖이거나 파란색일 때
            else:
                #방향 전환
                cd = change_directions[d]
                chess_pieces[id]['direction'] = cd
                #이동할 위치
                dr = r + directions[cd][0]
                dc = c + directions[cd][1]
                #범위 내부이고, 파란색이 아닐 때
                if (0 <= dr < N and 0 <= dc < N) and chess_board[dr][dc] != 2:
                    #빨간색일 때 move_pieces 뒤집기
                    if chess_board[dr][dc] == 1:
                        move_pieces = move_pieces[::-1]
 
                    #말 이동
                    pieces_count[(dr, dc)].extend(move_pieces)
                    for mp in move_pieces:
                        chess_pieces[mp]['location'] = (dr, dc)
                #범위 밖이거나, 파란색일 때
                else:
                    #제자리
                    dr, dc = r, c
                    pieces_count[(dr, dc)].extend(move_pieces)
 
            #현재 말이 추가된 칸의 말 갯수 확인
            if len(pieces_count[(dr, dc)]) >= 4:
                break_flag = True
                break
 
        #말 4개 이상이면 while 반복문 종료
        if break_flag:
            break
 
        #진행된 턴 수 증가
        play_count += 1
 
    #턴 수 출력
    print(play_count)

 

 

5. 고민

• 2차원 배열 1개, 딕셔너리 2개,,,,데이터를 더 적게 굴릴 수 있지 않나?
• 함수를 만드는 걸로 기능을 따로 빼주는 게 더 깔끔했을까?