Q10 자물쇠와 열쇠

domybest·2021년 4월 12일
0

실전 문제

목록 보기
9/34

풀이 코드

알고리즘

문제의 핵심은 2가지이다. 아이디어를 떠올렸는가? 배열을 회전하는 것에 대해 알고 있는가?
배열을 회전하는 문제에 관해선 처음 접해 보기 때문에 차근차근 회전에 관한 것부터 정리하였다. (이전 게시글 참조)
이제 아이디어만 떠올리면 되겠다. 먼저 기억하자. 생각하는 아이디어가 복잡해진다면 과감하게 버리고 다른 생각을 해 보자 라는 것. 필자는 말도 안되는 해결책을 고민하다가 시간을 많이 날렸다. 다른 문제에서도 자주 그랬다. 삐져 나와서 맞춰도 열쇠를 맞춘 것으로 인정한다고 문제에서 주어졌다. 여기서 힌트를 얻어보자. '삐져나온다', 그렇다면 lock 배열을 크게 만들어 버린다. 원래 lock배열의 원소들을 가운데에 딱 맞춰 넣기 위해 3배의 크기로 늘린다. 그 후 key 배열을 한 칸씩 이동하면서 lock 배열과 모두 더한다. 그 후 중앙의 원래 lock 배열의 원소가 '모두' 1이 되는 상황이 존재하면 가능, 존재하지 않으면 불가능을 리턴하면 된다.

핵심은 ' lock 배열을 3배 크게 만든 후 key 배열을 한 칸씩 이동하며 더하면서 lock 배열이 모두 1이 되는지를 확인 ' 하는 것이다. 이 아이디어를 코드로 옮기는 것은 어렵지 않다. 하지만 반복문의 변수가 굉장히 많이 나오므로 헷갈리지 않도록 주의해야 한다. 또한 n과 m은 20 이하로 주어졌기 때문에 완전 탐색을 시작부터 고려 해 봐야 하고 완전 탐색문제가 맞다.

package code;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class solve{
static void dfs(int[][] arr) {
int[][] result = new int[3][3];
result[1][1] = 1;
arr = result.clone();
}
public static void main(String[] args) throws Exception{
int[][] arr = new int[3][3];
dfs(arr);
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}

다음과 같은 코드에서 arr[1][1]은 1로 바뀔것 같지만 그렇지 않다. 그대로 0으로 출력된다. 이유에 대해 공부해보자.
profile
기억할 때 까지 반복!

0개의 댓글