- 소요시간 : 3시간
- 문제 사이트 : 백준
- 문제 수준 : 골드 2
- 문제 유형 : 구현, 브루트포스 알고리즘, 시뮬레이션, 백트래킹
- 다른 사람의 풀이를 참고 했는가 ? : X
- 한 번 풀었다가 다시 푸는 문제인가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/12100
- 푼 날짜 : 2023.03.26
1. 사용한 자료구조 & 알고리즘
모든 조합 (Left - Left - Left - Left - Left 부터
Down - Down - Down - Down - Down까지 ) 모든 경우의 수를 구하는 데에서 백트래킹을, 사용. 그리고 다음으로 왼쪽, 오른쪽, 위, 아래로 옮기는 것은 구현했다.
2. 사고과정
백트래킹으로 구하는 것도 알았지만 왼쪽, 오른쪽으로 한 번에 옮겨주고 또 이미 한 번 합쳐진 것은 또 합치지 않는 등의 작업을 해주는 것이 까다로웠다.
전체적인 코딩은 1시간 10분 정도만에 다했다.
하지만 제출해도 통과하지 못해서
12100 반례모음집 을 참고해서 문제를 풀기로 했다. 거기있는 테스트케이스 중 상당수를 통과하지 못해서 오류를 잡는데에만 거의 2시간을 썼다.
원인은 깊은 복사 - 얕은 복사 에 있었다. ㅠㅠ
left, right , up , down 을 할 때 메소드에 넘겨줄 때 얕은 복사를 해서 넘겨줘야하는데 깊은 복사를 해서 넘겨주는 바람에 오류가 났던 것 !!
사실 메소드에 넘겨줄 때 배열을 넘겨주면 그 배열은 메소드 내에서 새로 만들어진 배열이라 주소값이 다를 줄 알았는데 같았다. 충격이었다.
이 사실을 몰라서 2시간 동안 삽질했다.
하지만 그만큼 엄청 중요한 사실을 알게 돼서 앞으로는 절대 안까먹을 듯!!
3. 풀이과정
- 우선 메소드를 통해서 위, 아래, 왼쪽, 오른쪽으로 이동시키는 것을 구현한다.
- 그리고 백트래킹으로 left를 5번 하는 것 부터 down을 5번 하는 것 까지 모든 경우의 수를 고려해서 직업한다.
- depth가 5가 되면 return 한다.
- left, right, up, down 해줄 때마다 max 값을 갱신한다.
- 최종적으로 max 값을 출력
4. 소스코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb=new StringBuilder();
static int max=0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n=Integer.parseInt(br.readLine());
int originalMap[][]=new int[n][n];
for(int i=0;i<n;i++) {
st=new StringTokenizer(br.readLine());
for(int j=0;j<n;j++) {
originalMap[i][j]=Integer.parseInt(st.nextToken());
}
}
dfs(originalMap,0);
System.out.println(max);
}
public static void dfs(int nowMap[][],int depth) {
if(depth==5) {
return;
}
int map1[][]=new int[nowMap.length][nowMap.length];
int map2[][]=new int[nowMap.length][nowMap.length];
int map3[][]=new int[nowMap.length][nowMap.length];
int map4[][]=new int[nowMap.length][nowMap.length];
for(int i=0;i<map1.length;i++) {
map1[i]=nowMap[i].clone();
map2[i]=nowMap[i].clone();
map3[i]=nowMap[i].clone();
map4[i]=nowMap[i].clone();
}
dfs(left(map1),depth+1);
dfs(right(map2),depth+1);
dfs(up(map3),depth+1);
dfs(down(map4),depth+1);
}
public static int [][] left(int map[][]) {
int standard=0;
int indexI=0;
int indexJ=0;
int mapping[][]=new int[map.length][map.length];
for(int i=0;i<map.length;i++) {
standard=0;
for(int j=0;j<map.length;j++) {
if(map[i][j]==0) {
continue;
}
else if(standard==0) {
standard=map[i][j];
indexI=i;
indexJ=j;
}
else if(map[i][j]==standard) {
map[indexI][indexJ]*=2;
map[i][j]=0;
standard=0;
}
else {
standard=map[i][j];
indexI=i;
indexJ=j;
}
}
}
for(int i=0;i<mapping.length;i++) {
int cnt=0;
for(int j=0;j<mapping.length;j++) {
if(map[i][j]!=0) {
mapping[i][cnt++]=map[i][j];
}
max=Math.max(map[i][j],max);
}
}
return mapping;
}
public static int[][] right(int map[][]) {
int standard=0;
int indexI=0;
int indexJ=0;
int mapping[][]=new int[map.length][map.length];
for(int i=0;i<map.length;i++) {
standard=0;
for(int j=map.length-1;j>=0;j--) {
if(map[i][j]==0) {
continue;
}
else if(standard==0) {
standard=map[i][j];
indexI=i;
indexJ=j;
}
else if(map[i][j]==standard) {
map[indexI][indexJ]*=2;
map[i][j]=0;
standard=0;
}
else {
standard=map[i][j];
indexI=i;
indexJ=j;
}
}
}
for(int i=0;i<mapping.length;i++) {
int cnt=map.length-1;
for(int j=map.length-1;j>=0;j--) {
if(map[i][j]!=0) {
mapping[i][cnt--]=map[i][j];
}
max=Math.max(map[i][j],max);
}
}
return mapping;
}
public static int[][] up(int map[][]) {
int standard=0;
int indexI=0;
int indexJ=0;
int mapping[][]=new int[map.length][map.length];
for(int i=0;i<map.length;i++) {
standard=0;
for(int j=0;j<map.length;j++) {
if(map[j][i]==0) {
continue;
}
else if(standard==0) {
standard=map[j][i];
indexI=i;
indexJ=j;
}
else if(map[j][i]==standard) {
map[indexJ][indexI]*=2;
map[j][i]=0;
standard=0;
}
else {
standard=map[j][i];
indexI=i;
indexJ=j;
}
}
}
for(int i=0;i<mapping.length;i++) {
int cnt=0;
for(int j=0;j<mapping.length;j++) {
if(map[j][i]!=0) {
mapping[cnt++][i]=map[j][i];
}
max=Math.max(map[i][j],max);
}
}
return mapping;
}
public static int[][] down(int map[][]) {
int standard=0;
int indexI=0;
int indexJ=0;
int mapping[][]=new int[map.length][map.length];
for(int i=0;i<map.length;i++) {
standard=0;
for(int j=map.length-1;j>=0;j--) {
if(map[j][i]==0) {
continue;
}
else if(standard==0) {
standard=map[j][i];
indexI=i;
indexJ=j;
}
else if(map[j][i]==standard) {
map[indexJ][indexI]*=2;
map[j][i]=0;
standard=0;
}
else {
standard=map[j][i];
indexI=i;
indexJ=j;
}
}
}
for(int i=0;i<mapping.length;i++) {
int cnt=map.length-1;
for(int j=map.length-1;j>=0;j--) {
if(map[j][i]!=0) {
mapping[cnt--][i]=map[j][i];
}
max=Math.max(map[i][j],max);
}
}
return mapping;
}
}5. 결과
어제 계속 못풀었었는데 오늘 결국 풀었다
인간 승리 !!
6. 회고
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int map[]=new int[5];
System.out.println(map);
function(map);
}
public static void function(int nowMap[]) {
System.out.println(nowMap);
}
}결과 : 
새로 알게 된 사실 :
메소드 내에 배열을 넘겨주면 깊은 복사가 된다 ..!!
그래서 메소드 내에서 어떤 작업을 해도
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int map[]=new int[5];
function(map);
for(int i=0;i<map.length;i++) {
System.out.print(map[i]+" ");
}
}
public static void function(int nowMap[]) {
for(int i=0;i<nowMap.length;i++)
nowMap[i]=i+1;
}
}결과 : 
밖에서도 동일한 처리가 된다.
이걸 왜 이제 알았니??
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
아이스 카라멜 마끼아또보단 뜨거운 아메리카노를, 맨투맨보단 니트를, 웹툰보단 책을 좋아하고 싶은 사람