[문제]
현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
board는 4 x 4 크기의 2차원 배열입니다.
board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
0은 카드가 제거된 빈 칸을 나타냅니다.
1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
r은 커서의 최초 세로(행) 위치를 의미합니다.
c는 커서의 최초 가로(열) 위치를 의미합니다.
r과 c는 0 이상 3 이하인 정수입니다.
게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.
문제풀이
- 범위가 좁다. 완전탐색이 가능한가? 4*4격자에 타일은 6개까지이다. BFS나 DFS가 충분히 가능한 범위이다.
- 만약 BFS로 풀이한다면 첫 커서에서 가장가까운 카드를 고르는게 맞을까? 만약 겹친형식의 카드라면? 1 2 2 1인데 커서가 0,0부터 시작하면 1을 선택시 2를 먼저 선택한것보다 느리다.
- 따라서 모든카드를 한번씩은 탐색해봐야한다. 1카드를 먼저 골랐을때 2카드. 2카드를 골랐을때 1카드. 순열이 필요하다.
따라서 순열로 나온 카드조합을 순서대로 가는것의 최소치를 구해 마지막에 구해주면 된다.
순열 카드조합 구하기 -> BFS를 통한 최소치 구하기 -> 정답 리턴
코드
import java.util.*;
class Solution {
static HashSet<Integer> set;
static boolean[] visitPerm;
static int answer;
static int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int[] dx = {1,-1,0,0};
int[] dy = {0,0,1,-1};
public int solution(int[][] board, int r, int c) {
answer = Integer.MAX_VALUE;
visitPerm = new boolean[7];
set = new HashSet<>();
for(int i=0; i<4; i++) {
for(int j=0; j<4; j++) {
if(board[i][j] == 0) continue;
set.add(board[i][j]);
}
}
Perm(0, new int[set.size()], board, r, c);
return answer+1;
}
//순열 카드조합 만들기
void Perm(int count, int[] arr, int[][] board, int r, int c) {
if(set.size() == count) {
bfs(board, arr, r, c);
return;
}
for(int i=1; i<=6; i++) {
if(!set.contains(i) || visitPerm[i]) continue;
visitPerm[i] = true;
arr[count] = i;
Perm(count+1, arr, board, r, c);
visitPerm[i] = false;
}
}
//bfs돌리기
void bfs(int[][] board, int[] arr, int sr, int sc) {
Queue<int[]> q = new LinkedList<>();
boolean[][] visit = new boolean[4][4];
boolean[][] boardVisit = new boolean[4][4];
int count =0;
int idx =0;
boolean flag = false;
q.add(new int[]{sr,sc});
visit[sr][sc] = true;
while(!q.isEmpty()) {
int len = q.size();
for(int l=0; l<len; l++) {
int[] now =q.poll();
if(board[now[0]][now[1]]==arr[idx] && !boardVisit[now[0]][now[1]]){
boardVisit[now[0]][now[1]] = true;
q.clear();
visit = new boolean[4][4];
q.add(new int[]{now[0],now[1]});
visit[now[0]][now[1]] = true;
if(!flag){
flag= true;
}else{
flag = false;
idx++;
if(idx >= arr.length) {
answer = Math.min(answer, count);
return;
}
}
break;
}
for(int i=0;i<4;i++){
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if(!safe(nx,ny)||visit[nx][ny])continue;
visit[nx][ny]= true;
q.add(new int[]{nx,ny});
}
//Ctrl + 움직임
for(int i=0;i<4;i++){
int nx = now[0];
int ny = now[1];
//범위 끝이면 종료되는 while문
while(safe(nx+dx[i],ny+dy[i])){
nx+=dx[i];
ny+=dy[i];
if(!boardVisit[nx][ny]&&board[nx][ny]!=0) break;
}
if(!safe(nx,ny)||visit[nx][ny])continue;
visit[nx][ny]= true;
q.add(new int[]{nx,ny});
}
}
count++;
}
}
boolean safe(int x, int y) {
return 0<=x && x<4 && 0<=y && y<4;
}
}순열까지는 어떻게 구했으나 BFS 구현때 막혀 다른사람 코드를 참고했다.
생각해보면 모든 상황을 visit으로 표현하기만 했다면 간단했을 문제였던거 같다.
not null