본문 바로가기
알고리즘/백준

[백준 17837] 새로운 게임 2 (C++)

by Bloofer 2020. 3. 5.

A. 문제설명

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

문제의 자세한 설명은 위 링크에 자세하게 나와있으니 각설하고, 핵심을 요약하자면

 

1. N * N 체스판이 존재

2. 각 체스판의 엔트리에는 흰색 / 빨간색 / 파란색으로 표시

3. 체스판 위에 말들을 올림(숫자)

4. 각 말들은 이동방향이 정해져있고, 각 턴마다 해당 방향으로 한칸씩 이동

5. 각 말들은 이미 다른 말이 점유하고 있는 칸으로도 이동할 수 있는데, 

   5-1. 말 A가 말 B가 있는 위치로 이동하면 위에 올라탈 수 있음. 즉 A | B 에서 | A/B 로 올라타게 됨

   5-2. 이미 말 여러개가 겹쳐져 있는 칸에서 말이 이동시, 위에 태우고 있는 말들을 같이 이동시킴. 즉 A/B | C 에서 B가 C쪽으로 이동하면 | A/B/C로 A/B가 함께 C위에 올라타게 됨

6. 각 체스판의 엔트리 색상에 따라 말들에게 조건이 걸림

   6-1. 흰색일때: 아무 조건 없음

   6-2. 빨간색일때: 이동 후, 이동한 말들이 여러개라면 올라탄 순서를 반대로 바꿈. 즉, A/B | C 에서 B가 C쪽으로 이동하면 | A/B/C 가 아니라 | B/A/C가 됨

   6-3. 파란색일때: 이동 불가. 벽이랑 같다고 보면 됨

7. 체스판 / 말들이 주어졌을 때 매 턴마다 말들이 이동해서 말이 4개이상 같은 칸에 쌓이면 종료

 

사실, 그렇게 어려운 문제는 아닌데 조건이 까다로운 게 많다. 정리하고 보면 의외로 간단한데 결국 5번과 6번의 조건을 문제에서 제시한 그대로 구현하면 되는 문제

 

B. 접근법

전형적인 시뮬레이션 문제. 문제에서 제약조건으로 1000번의 턴까지 보기로 했으니 1000번의 시뮬레이션 안에서 답이 나오면 그걸 내면 되고 아니면 -1 반환

 

C. 풀이

1. 1000번의 턴을 수행하는 반복문

2. 각 K개의 말들이 현재 위치에서 이동방향을 보고 이동 가능한지 확인

   2-1. 이동불가하면(벽이거나 파란색일때) 현재 위치 유지하며 방향 뒤집음

   2-2. 이동가능하면 현재 위치에서 업은 말들 포함하여 다음 위치로 이동

3. 다음 위치에 있는 말들 위에 업힌다.

4. 만약 다음 위치가 빨간색이면 말들의 업힌 순서를 뒤집고, 하얀색이면 그대로 둠

   * 기존에 있던 빨간색 셀 안의 말들은 그대로 두고 새로 들어온 스택의 말들만 뒤집어서 넣는다.

   * 뒤집을 때의 조건을 셀 안의 전체 말을 뒤집는 것으로 하면 원하는 결과가 나오지 않음

5. 업힌 말의 총 갯수가 4개이상이면 종료

 

D. 내 코드