❓ 윷놀이(Small)
🏷️ 관련 주제 : DFS Recursion Map
💦 나의 시도
먼저 입력값들을 하나씩 처리하였습니다.
던진 윷의 이동 칸 수를 저장할 때에는 큐 자료구조를 사용하였습니다.
먼저 Map에 Do ~ Mo를 키로 이동할 칸 수를 값으로 하여 저장 후,
입력값을 처리할 때 각 키 값으로 이동 칸 수를 조회하여 Queue<Integer> q에 담아주었습니다.
그리고 A팀과 B팀의 말의 위치를 담을 자료구조로는 처음에 이차원 int 배열을 사용하였으나
DFS 탐색 시, 이차원 배열에서 현재 말의 위치를 반복문을 통해 찾는 것은 Map이 O(1)으로 더 빠르므로
최종적으로 Map<Integer, Integer> 배열을 사용하여 각 인덱스에 해당하는 Map에 말의 위치를 키로 저장해 주었습니다.
(A팀 : 0번 인덱스, B팀 : 1번 인덱스)
용이가 복구한 말의 위치는 인스턴스 변수로 target변수에 저장하였습니다.
- 키 : 각 팀의 말 위치 번호
- 값 : 1 (말의 수는 체크하지 않으므로 임의의 값으로 지정)
그리고 DFS 탐색 시, 말을 이동하기 위해 Map<Integer, Integer> 배열 map을 만들었습니다.
- 0번 인덱스의 Map : A 팀의 말 위치 및 수 저장
- 1번 인덱스의 Map : B 팀의 말 위치 및 수 저장
- Map의 Key-Value
- 키 : 말의 위치
- 값 : 해당 위치에 말의 수
-1키 값에 아직 출발하지 않은 말의 수 저장
입력값 처리를 하고 나니
말 이동, 다음 턴 구하기, 말 잡기, 업기 등 다양한 규칙으로 한번에 쉽게 코드가 써지지는 않습니다.
그래서 먼저 주석으로 제가 처리해야할 동작들을 정리해 보았습니다.
그리고 해당 동작들을 메서드로 하나씩 만들어 보았습니다.
먼저 말의 시작 위치 start와 이동 칸 수 move를 매개 변수로
말이 도착할 위치 번호를 반환하는 메서드 moveHorse()를 만들었습니다.
다음으로 매개변수로 모든 팀의 말의 위치가 담긴 Map<Integer, Integer> 배열 map을 주면
용이가 정리한 말의 위치가 담긴 인스턴스 변수 target과 키를 비교하여
그 결과를 boolean형으로 반환하는 sameArrange() 메서드를 만들었습니다.
마지막으로 DFS를 하기 위해
모든 팀의 말의 위치 Map<Integer, Integer> 배열 map, 현재 팀의 순서 int team, 현재 이동할 말의 위치 int curIdx, 던진 윷의 정보가 담긴 Queue<Integer> moves를 매개변수로 받아
다음 팀의 순서(A팀: 0, B팀: 1) 혹은 게임이 끝났거나 moves가 비었을 때, 용이가 정리한 말의 위치와 현재 탐색 결과 말의 위치를 비교한 결과(일치 : 2, 불일치 : -1)를 반환하는 메서드 arrangeHorse() 메서드를 만들었습니다.
그리고 main 메서드에서 arrangeHorse()메서드를 호출하였습니다.
A팀부터 시작이므로 team은 0,
아직 출발한 말들이 없으므로 curIdx는 -1로 하여 해당 메서드를 호출하고
그 결과를 int result에 담아
result가 2이면 BufferedWriter에 "Case #" + i + ": YES\n"를 쓰고
-1이면 "Case #" + i + ": NO\n"를 쓰도록 하였습니다.
그리고 모든 테스트 케이스가 종료되면 BufferedWriter를 종료하여 모든 문자열을 출력하도록 하였습니다.
❌ 틀렸습니다.
50% 정도까지 통과되다가 '틀렸습니다.'가 뜨는데 반례를 쉽게 찾지 못하여 결국 해결하지 못하였습니다.
질문 게시판에도 질문이 하나도 없어서 크게 도움 받지 못하였는데
틀린 이유가 뭘까요?
설이 끝나고 아직 문제를 포기할 수 없었습니다. 다시 틀린 이유를 찾기 위해 코드를 다시 읽어보았습니다.
불필요한 조건부가 보여 코드를 수정하다 moveHorse() 메서드가 조금 이상한 것을 발견하였습니다.
10 - 25 - 26 - 22 - 27 -28 - 0으로 말이 지나가는 부분의 가운데가 22인데 그냥 (24 + move)로 계산한 부분이 있어서moveHorse()메서드를 수정하기 시작하였습니다.
윷판을 다시 만들어 볼까? 고민하였습니다.
이걸 어떻게 구현하지 생각하며 LinkedList도 찾아보고 했는데
그냥 기존 메서드의 switch-case문에서 결과값을 바로 int형으로 반환하였다면
수정한 코드에서는 지름길로 빠질 수 있는 위치에서는 재귀함수를 호출하도록 수정하였습니다.
기존 moveHorse() 메서드
<pre class="java"><code>public static int moveHorse(int start, int move) {
switch (start) {
case 0 : return 30;
case -1 : return move;
case 5 : return 19 + move;
case 10 : return 24 + move;
case 22 : {
int nextIdx = 26 + move;
if (nextIdx > 29) {
return 30;
}
return nextIdx % 29;
}
default : {
int nextIdx = start + move;
if (start >= 20 && start <= 24 && nextIdx > 24) {
return start + move - 10;
}
if (start >= 15 && start <= 19) {
if (nextIdx > 20) {
return 30;
}
return nextIdx % 29;
}
return (nextIdx > 29) ? 30 : nextIdx % 29;
}
}
}</code></pre>맞았습니다!!
- 메모리 : 15176 KB
- 시간 : 136 ms
- 코드 길이 : 5695 B
📑제출 기록 및 오답 원인
💯 해결 방법
import java.io.*;
import java.util.*;
public class Main {
public static Map<Integer, Integer>[] target;
public static int U;
public static int N;
public static int A;
public static int B;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
Map<String, Integer> move = new HashMap<>(Map.of(
"Do", 1,
"Gae", 2,
"Gul", 3,
"Yut", 4,
"Mo", 5
));
for (int i = 1; i <= T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
U = Integer.parseInt(st.nextToken()); // 한 팀에서 사용가능한 말의 수
N = Integer.parseInt(st.nextToken()); // 던져진 윷의 목록 개수
A = Integer.parseInt(st.nextToken()); // 판 위에 놓여 있는 A팀 말의 개수
B = Integer.parseInt(st.nextToken()); // 판 위에 놓여 있는 B팀 말의 개수
Queue<Integer> q = new LinkedList<>();
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
q.offer(move.get(st.nextToken()));
}
target = new HashMap[2];
target[0] = new HashMap<Integer, Integer>();
target[1] = new HashMap<Integer, Integer>();
for (int k = 0; k < 2; k++) {
st = new StringTokenizer(br.readLine());
int bound = (k == 0) ? A : B;
for (int j = 0; j < bound; j++) {
target[k].put(Integer.parseInt(st.nextToken()), 1);
}
}
Map<Integer, Integer>[] map = new HashMap[2]; // 29 : 한 바퀴 돌아 0, 30 : 완주, 31 : 시작 전
map[0] = new HashMap<>(Map.of(-1, U));
map[1] = new HashMap<>(Map.of(-1, U));
int result = arrangeHorse(map, 0, -1, q);
switch (result) {
case 2 : {
bw.write("Case #" + i + ": YES\n");
break;
}
case -1 : {
bw.write("Case #" + i + ": NO\n");
break;
}
default : bw.write("Case #" + i + ": NO\n");
}
}
bw.close();
}
public static int arrangeHorse(Map<Integer, Integer>[] map, int team, int curIdx, Queue<Integer> moves) {
int move = moves.poll();
int nextIdx = moveHorse(curIdx, move);
if (nextIdx == 30) {
map[team].remove(curIdx);
if (moves.isEmpty() && sameArrange(map)) {
return 2;
}
return -1;
}
int nextTeam = (move >= 4) ? team : 1 - team;
int curCnt = 1;
if (curIdx == -1) {
if (!map[team].containsKey(curIdx)) {
return -1;
}
if (map[team].get(curIdx) == 1) {
map[team].remove(curIdx);
} else {
map[team].put(-1, map[team].get(-1) - 1);
}
} else {
curCnt = map[team].get(curIdx);
map[team].remove(curIdx);
}
map[team].put(nextIdx, map[team].getOrDefault(nextIdx, 0) + curCnt);
if (map[1 - team].containsKey(nextIdx)) {
map[1 - team].put(-1, map[1 - team].getOrDefault(-1, 0) + map[1 - team].get(nextIdx));
map[1 - team].remove(nextIdx);
nextTeam = team;
}
if (moves.isEmpty()) {
if (sameArrange(map)) {
return 2;
}
return -1;
}
Set<Integer> horses = map[nextTeam].keySet();
for (int horse : horses) {
Queue<Integer> copyMoves = new LinkedList<>(moves);
Map<Integer, Integer>[] copyMap = new HashMap[2];
copyMap[0] = new HashMap<>(map[0]);
copyMap[1] = new HashMap<>(map[1]);
int nextTeam2 = arrangeHorse(copyMap, nextTeam, horse, copyMoves);
if (nextTeam2 == 2) {
return 2;
}
}
return -1;
}
public static int moveHorse(int start, int move) {
if (move == 0) {
return start;
}
switch (start) {
case -1 : return move;
case 0 : return 30;
case 5 : return moveHorse(20, move - 1);
case 10 : return moveHorse(25, move - 1);
case 22 : return moveHorse(27, move - 1);
case 25 : return moveHorse(26, move - 1);
case 26 : return moveHorse(22, move - 1);
case 27 : return moveHorse(28, move - 1);
case 28 : return moveHorse(0, move - 1);
}
int nextIdx = start + move;
if (start >= 20 && start <= 24 && nextIdx > 24) {
return nextIdx - 10;
}
if (start >= 15 && start <= 19) {
if (nextIdx > 20) {
return 30;
}
return nextIdx % 20;
}
return nextIdx;
}
public static boolean sameArrange(Map<Integer, Integer>[] map) {
for (int i = 0; i < 2; i++) {
Set<Integer> keys = new HashSet(map[i].keySet());
keys.remove(-1);
Set<Integer> keysTarget = target[i].keySet();
if (!keys.equals(keysTarget)) {
return false;
}
}
return true;
}
}
