@재귀, 순열, 시뮬레이션 / 2h 5m
필기 22m 포함 코드 구현하는데 총 50m
그런데 디버깅 하는데에 1h 5m..ㅠㅠ
4%에서 계속 틀렸습니다가 뜨는데, 질문게시판의 테케를 아무리 돌려도 다 맞게 나와서 멘붕왔었다.
딱 이거 하나만 틀리게 나와서 간신히 찾았다ㅠ
4%대에서 틀리시는 분들이 참고하시면 좋을 듯
20
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024
내 코드에는 인덱스를 관리하는 부분에 문제가 있었다.
문제 링크
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
구현 방법
1. 재귀를 이용하여 크기가 5인 순열을 만든다. 넣을 값은 각 방향을 나타내는 0, 1, 2, 3이다
2. 한 순열이 만들어질 때마다
1) copyMap을 만들고
2) 순열의 방향에 따라 게임을 진행한다
3) 마지막으로 가장 큰 값을 체크한다
이 과정을 반복한다.
게임 진행 방법 - 기울여서 값 합치기
+ 나는 한 함수로 다 구현할 자신이 없어서, 방향마다 각각 구현했다.
장점은 - 한 함수로 하려고 머리쓰다가 망할 가능성이 적다.
단점은 - 4방향 복붙하다가 어디 한군데를 안고치거나, 인덱스를 실수하면 찾기 힘들다.
일단 위로 기울이는 방향(d==0)을 기준으로 설명하자면
for (j: 0~N-1까지의 열) {
for (i: 0~ N-1까지의 행) {
if (만약 지금 맵의 값이 0이 아니라면) {
지금 행의 값을 idx에 저장해두고;
while문을 돌면서 아래 행에서 0이 아닌 값을 찾는다;
if (i가 N보다 작은데) { //0이 아닌 값을 찾았다는 의미
if (그 값과 아까 저장한 idx행의 값이 같다면) {
idx행의 칸에 값을 두배 해주고;
지금 칸은 0으로 만들어준다;
i++;
//여기서 지금 칸은 더 이상 볼 필요가 없으니 다음 칸으로 넘어가라고 i++를 해줬는데,
//다음 for문을 돌면서 i가 어차피 추가되므로 여기서 이걸 해주면 안된다. 그럼 오히려 한 칸을 건너뛰어 버린다 ㅠㅠ
} else {
i--;
//여기서는 오히려 해줘야한다. 지금 보고 있는 칸과 그 다음 칸을 비교해야 하므로,
//그대로 두면 지금 칸을 넘어가버리기 때문에 다음 턴에도 이번 칸을 보도록 -- 해줘야한다!
}
}
}
} // i for문 end
//한 줄을 다 밀고 나서, 여기서 push를 해 줘야 한다. for문 안에서 해줬다가 계속 틀렸음 ㅠ
} // j for문 end
게임 진행 방법 - 값 합친 후 밀어주기
합치는 부분과 로직은 거의 비슷하다.
이 부분도 위와 마찬가지로 위로 기울이는 방향(d==0)을 기준으로 설명하자면
한 열을 기준으로
for (i: 0~N-1) {
if (지금 칸의 값이 0이면) {
idx에 지금 행의 값을 저장해두고;
while문을 돌면서 아래 행에서 0이 아닌 값을 찾는다;
if (i가 N보다 작다면) { //0이 아닌 값을 찾았다는 의미
아까 저장한 idx행에 지금 값을 넣어주고;
지금 칸의 값을 0으로 만들어준다;
그리고 지금 i에 idx 값을 넣어준다;
//여기서도 i = idx + 1; 했다가.. for문 돌면서 ++이 한번 더 돼서 다음칸을 건너뛰어 버렸다ㅠㅠ 조심!
}
}
}
시간 줄이기
while문을 빠져나오고 나서
if (i == N) break; 이 코드를 매번 넣어줬었는데, 이 부분을 제거하니 시간이 40ms 가량 줄었다.
어차피 저 코드가 없어도 i가 N이면 더이상 for문이 돌지 않으므로 의미 없는 코드이다.
+ 그리고 가지치기를 하려고
maxVal이 이 문제에서 가장 커질 수 있는 값인 2^15일때 반복을 종료하라는 코드를 넣었었는데,
오히려 이 코드가 없을 때 더 빨리 돌았다 -> 즉, 이것 또한 필요 없는 코드!
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int N, map[][], copyMap[][], maxVal = 0, permu[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
copyMap = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
permu = new int[5];
permu(5, 0);
System.out.println(maxVal);
}
private static void permu(int n, int k) {
if (n == k) {
copyMapMake();
allMove();
maxCheck();
//이거 필요 없음! 없는 게 오히려 더 빠르다
//if (maxVal == (int)Math.pow(2, 15)) {
// System.out.println(maxVal);
// System.exit(0);
//}
return;
}
for (int i = 0; i < 4; i++) {
permu[k] = i;
permu(n, k + 1);
permu[k] = 0; //안해줘도 되지만 의미 상
}
}
private static void allMove() {
for (int i = 0; i < 5; i++)
move(permu[i]);
}
private static void move(int d) {
if (d == 0) {
for (int j = 0; j < N; j++) {
for (int i = 0; i < N; i++) {
if (copyMap[i][j] != 0) {
int idx = i;
while (++i < N && copyMap[i][j] == 0);
if (i < N) { //값을 합친다면
if (copyMap[idx][j] == copyMap[i][j]) {
copyMap[idx][j] *= 2;
copyMap[i][j] = 0;
} else { //값을 합치지 않는다
i--;
}
}
}
}
push(d, j);
}
} else if (d == 1) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (copyMap[i][j] != 0) {
int idx = j;
while (++j < N && copyMap[i][j] == 0);
if (j < N) { //값을 합친다면
if (copyMap[i][idx] == copyMap[i][j]) {
copyMap[i][idx] *= 2;
copyMap[i][j] = 0;
} else { //값을 합치지 않는다
j--;
}
}
}
}
push(d, i);
}
} else if (d == 2) {
for (int j = 0; j < N; j++) {
for (int i = N - 1; i >= 0; i--) {
if (copyMap[i][j] != 0) {
int idx = i;
while (--i >= 0 && copyMap[i][j] == 0);
if (i >= 0) { //값을 합친다면
if (copyMap[idx][j] == copyMap[i][j]) {
copyMap[idx][j] *= 2;
copyMap[i][j] = 0;
} else { //값을 합치지 않는다
i++;
}
}
}
}
push(d, j);
}
} else if (d == 3) {
for (int i = 0; i < N; i++) {
for (int j = N - 1; j >= 0; j--) {
if (copyMap[i][j] != 0) {
int idx = j;
while (--j >= 0 && copyMap[i][j] == 0);
if (j >= 0) { //값을 합친다면
if (copyMap[i][idx] == copyMap[i][j]) {
copyMap[i][idx] *= 2;
copyMap[i][j] = 0;
} else { //값을 합치지 않는다
j++;
}
}
}
}
push(d, i);
}
}
}
private static void push(int d, int xy) {
if (d == 0) {
for (int i = 0; i < N; i++) {
if (copyMap[i][xy] == 0) {
int idx = i;
while (++i < N && copyMap[i][xy] == 0);
if (i < N) {
copyMap[idx][xy] = copyMap[i][xy];
copyMap[i][xy] = 0;
i = idx;
}
}
}
} else if (d == 1) {
for (int j = 0; j < N; j++) {
if (copyMap[xy][j] == 0) {
int idx = j;
while (++j < N && copyMap[xy][j] == 0);
if (j < N) {
copyMap[xy][idx] = copyMap[xy][j];
copyMap[xy][j] = 0;
j = idx;
}
}
}
} else if (d == 2) {
for (int i = N - 1; i >= 0; i--) {
if (copyMap[i][xy] == 0) {
int idx = i;
while (--i >= 0 && copyMap[i][xy] == 0);
if (i >= 0) {
copyMap[idx][xy] = copyMap[i][xy];
copyMap[i][xy] = 0;
i = idx;
}
}
}
} else if (d == 3) {
for (int j = N - 1; j >= 0; j--) {
if (copyMap[xy][j] == 0) {
int idx = j;
while (--j >= 0 && copyMap[xy][j] == 0);
if (j >= 0) {
copyMap[xy][idx] = copyMap[xy][j];
copyMap[xy][j] = 0;
j = idx;
}
}
}
}
}
private static void maxCheck() {
int max = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (max < copyMap[i][j])
max = copyMap[i][j];
if (maxVal < max) maxVal = max;
}
private static void copyMapMake() {
for (int i = 0; i < N; i++)
copyMap[i] = map[i].clone();
}
}
이것 저것 다 해봤는데,
시간 줄이려고 넣은 코드 빼고, 불필요한 if문을 빼니 시간이 60ms가량 줄었다.
많은 것을 배울 수 있는 문제였다.
끝!
'algorithm > Baekjoon' 카테고리의 다른 글
| [백준] 17136.색종이 붙이기 (java) / 백트래킹, DFS (0) | 2020.02.24 |
|---|---|
| [백준] 17780.새로운 게임 (java) / 시뮬레이션 (0) | 2020.02.23 |
| [백준] 17281.⚾ 야구공 (java) / 시뮬레이션, Next-Permutation, 순열 (0) | 2020.02.12 |
| [백준] 17143.낚시왕 (java) / 시뮬레이션 (0) | 2020.02.11 |
| [백준] 16637.괄호 추가하기 (java) / DFS, 백트래킹, 조합, 시뮬레이션 (0) | 2020.02.10 |
댓글