들어가며
https://www.acmicpc.net/problem/12100
중학교 때인가..? 2048이라는 게임을 재밌게 했던 기억이 있다. 매우 반가웠지만,,, 문제를 읽고 나서 반갑지 않았다 ㅎㅎ. 상하좌우로 5번 움직였을 때 가장 수의 블록을 정답으로 출력하면 되는 문제였다.
본문으로
입력 크기는 최대 20이어서, 완전탐색으로 구현해도 충분히 괜찮은 문제였다. 하지만 고려해야할게 꽤 많아서 코드가 길어질 게 뻔했는데.. 딱히 방법이 안떠올라서 생각나는데로 쭉 작성했다... 시뮬레이션 문제는 정말 실수 하나 하면 미궁속으로 빠지는 것 같다.
public class Main {
static int N, ret;
static void go(int[][] maps, int idx) {
if (idx == 5) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
ret = Integer.max(maps[i][j], ret);
}
}
return;
}
// 오른쪽 밀기
go(right(maps), idx + 1);
// 아래로 밀기
go(down(maps), idx + 1);
// 왼쪽 밀기
go(left(maps), idx + 1);
// 위로 밀기
go(up(maps), idx + 1);
}
static int[][] right(int[][] maps) {
int[][] rMaps = makeNewMap(maps);
// 오른쪽으로 다 이동
for (int i = 0; i < N; i++) {
for (int j = N - 2; j >= 0; j--) {
if (rMaps[i][j] == 0) {
continue;
}
int cnt = 1;
while (j + cnt < N && rMaps[i][j + cnt] == 0) {
rMaps[i][j + cnt] = rMaps[i][j + cnt - 1];
rMaps[i][j + cnt - 1] = 0;
cnt++;
}
}
}
// 합치기
for (int i = 0; i < N; i++) {
for (int j = N - 2; j >= 0; j--) {
if (rMaps[i][j] == 0) {
continue;
}
if (rMaps[i][j + 1] == rMaps[i][j]) {
rMaps[i][j + 1] = rMaps[i][j + 1] * 2;
rMaps[i][j] = 0;
j--;
}
}
}
// 오른쪽으로 다 이동
for (int i = 0; i < N; i++) {
for (int j = N - 2; j >= 0; j--) {
if (rMaps[i][j] == 0) {
continue;
}
int cnt = 1;
while (j + cnt < N && rMaps[i][j + cnt] == 0) {
rMaps[i][j + cnt] = rMaps[i][j + cnt - 1];
rMaps[i][j + cnt - 1] = 0;
cnt++;
}
}
}
return rMaps;
}
static int[][] left(int[][] maps) {
int[][] lMaps = makeNewMap(maps);
// 왼쪽으로 다 이동
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (lMaps[i][j] == 0) {
continue;
}
int cnt = 1;
while (j - cnt >= 0 && lMaps[i][j - cnt] == 0) {
lMaps[i][j - cnt] = lMaps[i][j - cnt + 1];
lMaps[i][j - cnt + 1] = 0;
cnt++;
}
}
}
// 합치기
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (lMaps[i][j] == 0) {
continue;
}
if (lMaps[i][j - 1] == lMaps[i][j]) {
lMaps[i][j - 1] = lMaps[i][j - 1] * 2;
lMaps[i][j] = 0;
j++;
}
}
}
// 왼쪽으로 다 이동
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (lMaps[i][j] == 0) {
continue;
}
int cnt = 1;
while (j - cnt >= 0 && lMaps[i][j - cnt] == 0) {
lMaps[i][j - cnt] = lMaps[i][j - cnt + 1];
lMaps[i][j - cnt + 1] = 0;
cnt++;
}
}
}
return lMaps;
}
static int[][] up(int[][] maps) {
int[][] uMaps = makeNewMap(maps);
// 위로 다 이동
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (uMaps[j][i] == 0) {
continue;
}
int cnt = 1;
while (j - cnt >= 0 && uMaps[j - cnt][i] == 0) {
uMaps[j - cnt][i] = uMaps[j - cnt + 1][i];
uMaps[j - cnt + 1][i] = 0;
cnt++;
}
}
}
// 합치기
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (uMaps[j][i] == 0) {
continue;
}
if (uMaps[j - 1][i] == uMaps[j][i]) {
uMaps[j - 1][i] = uMaps[j - 1][i] * 2;
uMaps[j][i] = 0;
j++;
}
}
}
// 위로 다 이동
for (int i = 0; i < N; i++) {
for (int j = 1; j < N; j++) {
if (uMaps[j][i] == 0) {
continue;
}
int cnt = 1;
while (j - cnt >= 0 && uMaps[j - cnt][i] == 0) {
uMaps[j - cnt][i] = uMaps[j - cnt + 1][i];
uMaps[j - cnt + 1][i] = 0;
cnt++;
}
}
}
return uMaps;
}
static int[][] down(int[][] maps) {
int[][] dMaps = makeNewMap(maps);
// 아래로 다 이동
for (int i = 0; i < N; i++) {
for (int j = N - 2; j >= 0; j--) {
if (dMaps[j][i] == 0) {
continue;
}
int cnt = 1;
while (j + cnt < N && dMaps[j + cnt][i] == 0) {
dMaps[j + cnt][i] = dMaps[j + cnt - 1][i];
dMaps[j + cnt - 1][i] = 0;
cnt++;
}
}
}
// 합치기
for (int i = 0; i < N; i++) {
for (int j = N - 2; j >= 0; j--) {
if (dMaps[j][i] == 0) {
continue;
}
if (dMaps[j + 1][i] == dMaps[j][i]) {
dMaps[j + 1][i] = dMaps[j + 1][i] * 2;
dMaps[j][i] = 0;
j--;
}
}
}
// 아래로 다 이동
for (int i = 0; i < N; i++) {
for (int j = N - 2; j >= 0; j--) {
if (dMaps[j][i] == 0) {
continue;
}
int cnt = 1;
while (j + cnt < N && dMaps[j + cnt][i] == 0) {
dMaps[j + cnt][i] = dMaps[j + cnt - 1][i];
dMaps[j + cnt - 1][i] = 0;
cnt++;
}
}
}
return dMaps;
}
static int[][] makeNewMap(int[][] maps) {
int[][] dMaps = new int[N][N]; // 참조 끊어서 새로 만들어주기, 원복 안하려고.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dMaps[i][j] = maps[i][j];
}
}
return dMaps;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] maps = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
maps[i][j] = Integer.parseInt(st.nextToken());
}
}
ret = Integer.MIN_VALUE;
go(maps, 0);
System.out.println(ret);
}
}
정말 어찌저찌해서 디버깅해가면서 정답으로 출력했다... 근데 코드길이가 250줄이 넘어간다 ㅎㅎ. 절대 코딩테스트에서는 생각만 해도 끔직한 풀이이다.
코드를 줄일 수 있는 방법은 없을까? 지금 나의 로직은 다음과 같다.
- EX) 2 2 0 0 4
- 왼쪽으로 다 밀기 -> 2 2 4 0 0
- 합치기 -> 4 0 4 0 0
- 왼쪽으로 다 밀기 -> 4 4 0 0 0
- 이거를 왼, 오, 위, 아래.. 모든 로직이 존재한다 ㅎㅎ
이러니 코드가 300줄 가까이 되지 않나 싶다.
미는 로직을 통일하고 배열을 회전하면 로직을 통일시킬 수 있지 않을까!
지금 보면 당연한 말일 수도 있겠지만,, 방법을 정하고 로직 작성에 들어가버린 순간 위의 생각을 떠올리기가 쉽지 않다... 제한시간 안에 풀어야하는 코테 상황이면 더더욱...
그래서 미는 로직과 회전로직으로 아래와 같이 작성했다. 주석에 친절하게 설명도 넣어뒀다.
public class Main {
static int N, ret;
static void go(int[][] maps, int idx) {
if (idx == 5) {
findMax(maps);
return;
}
for (int i = 0; i < 4; i++) {
int[][] next = move(maps, i);
go(next, idx + 1);
}
}
static void findMax(int[][] maps) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (maps[i][j] == 0) {
continue;
}
ret = Math.max(ret, maps[i][j]);
}
}
}
static int[][] move(int[][] maps, int dir) {
int[][] next = maps;
// 왼쪽으로 미는 로직이 동일하게끔 90도 회전해주기.
// 90 회전 한번 하면 위로 밀기, 두번하면 왼쪽으로 밀기, 세번하면 아래로 밀기
for (int i = 0; i < dir; i++) {
next = rotate90(next);
}
// 왼쪽으로 밀기
next = moveLeft(next);
// 원상복귀 하기
for (int i = 0; i < (4 - dir) % 4; i++) { // 위로 옮기려고 한번 돌렸으면, 원상복귀하려면 4번돌려줘야함.
next = rotate90(next);
}
return next;
}
static int[][] rotate90(int[][] maps) {
int[][] rotated = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
rotated[j][N - i - 1] = maps[i][j];
}
}
return rotated;
}
// 보드를 왼쪽으로 한번 이동
static int[][] moveLeft(int[][] maps) {
int[][] next = new int[N][N];
for (int i = 0; i < N; i++) {
int[] line = new int[N];
for (int j = 0; j < N; j++) {
line[j] = maps[i][j];
}
int[] moved = work(line);
for (int j = 0; j < N; j++) {
next[i][j] = moved[j];
}
}
return next;
}
// 왼쪽으로 밀며 합치기
static int[] work(int[] line) {
List<Integer> nums = new ArrayList<>();
for (int i = 0; i < N; i++) {
if (line[i] != 0) {
nums.add(line[i]);
}
}
int[] result = new int[N];
int idx = 0;
for (int i = 0; i < nums.size(); i++) {
if (i + 1 < nums.size() && nums.get(i).equals(nums.get(i + 1))) {
result[idx] = nums.get(i) * 2;
i++;
idx++;
} else {
result[idx] = nums.get(i);
idx++;
}
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[][] maps = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
maps[i][j] = Integer.parseInt(st.nextToken());
}
}
ret = Integer.MIN_VALUE;
go(maps, 0);
System.out.println(ret);
}
}
코드가 거의 2배 이상 줄었다!
마무리하며
시뮬레이션 문제들은 요구사항들로 인해 코드가 길어지는 것 같다. 근데 문제를 꽤 풀다보니 그 요구사항들이 대부분 중복된다는 점을 최근에 깨달았다. 상하좌우로 이동시키는 것을 각각 구현하는 것이 아니라, 왼쪽으로 미는 것 하나만 구현해놓고 배열을 회전시키면 되는 것 아니겠나!!
대부분 시뮬레이션 문제들이 배열 회전으로 코드가 짧아지는 것을 느낀다. 코드가 길어질 수록 실수가 많이 발생할테니, 꼭 공통 로직을 생각해보고 문제풀이에 들어가는 버릇을 들여야겟다! 특히 배열 회전 정도는 어렴풋이 외우고 있자!~!!
'Problem Solve' 카테고리의 다른 글
| [JAVA] 17406 - 배열 돌리기 4 💛4 : 복잡한 2차원 배열 문제는 복잡도를 줄이기 위해 1차원으로 뽑자! (0) | 2026.03.31 |
|---|---|
| [JAVA] 3190 - 뱀 💛4 : 시뮬레이션.. 시뮬레이션.. 시뮬레이션..!!! (0) | 2026.03.30 |
| [JAVA] 17144 - 미세먼지 안녕! 💛4: 어려운 구현+시뮬레이션 문제 (0) | 2026.03.26 |
| [JAVA] 1700 - 멀티탭 스케줄링 💛1 : OS시간에 배웠던 Page Replacement 알고리즘 적용문제 (Optimal Page Replacement) (0) | 2026.03.25 |
| [JAVA] 13144 - List of Unique Numbers 💛4 : 투 포인터를 활용한 경우의 수 구하기 (0) | 2026.03.24 |