[프로그래머스]카드짝맞추기_Java

--문제--

https://programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

--문제 접근--

카카오 신입 공채 1차 온라인 코딩 테스트에서 정답률이 0.95%인 극악의 난이도의 문제입니다.

문제 풀이법은 DFS와 BFS를 고려하였는데 기저 조건 혹은 BFS 멈추는 조건을 어떻게 할지 생각이 나지 않아.. 카카오 문제 풀이법을 참고하였습니다.

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설

카카오 풀이법 링크입니다.

간략하게 말하면

카드 종류가 최대 6개 이므로 어떤 카드부터 제거해 나갈지 고민을 하는 방법은 6! 가지입니다.

그래서 순열을 통해 구하고 

그 순서대로 답을 구해보면 되는 방식입니다.

여기서 주의해야 할 점은 

①그냥 이동하는 방법과

②Crtl로 이동하는 방법을 고려해야 하는 것입니다.

• 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
  • 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
  • [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한 번에 이동합니다.
    • 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
  • 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.

여기서 주의할 점을 강조 표시했습니다.

저는 처음에 컨트롤은 무조건 끝으로 이동하는 줄 알고 계속 틀렸습니다.

--코드--

package Level3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class 카드짝맞추기 {
	public static void main(String[] args) {
		int[][] temp= {{1,0,0,3},{2,0,0,0},{0,0,0,2},{3,0,1,0}};
		System.out.println(solution(temp,1,0));
	}
	static ArrayList<int[]> list=new ArrayList<>();
	static int[] num;
	static boolean[] check;
	static class node{
		int x,y,cnt;
		public node(int x, int y, int cnt) {
			super();
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	static Queue<node> que;
	static int[] dr= {1,-1,0,0};
	static int[] dc= {0,0,1,-1};
	private static int solution(int[][] board, int r, int c) {
		int answer=1000000;
		int tmp=0;
		for(int i=0;i<board.length;i++) {
			for(int j=0;j<board[0].length;j++) {
				if(board[i][j]>tmp)tmp=board[i][j];
			}
		}
		check=new boolean[tmp+1];
		num=new int[tmp];
		permutation(tmp,0);
		for(int[] per:list) {
			int[][] tmpBoard=new int[board.length][board[0].length];
			//임시 보드 생성
			for(int i=0;i<board.length;i++) {
				System.arraycopy(board[i], 0, tmpBoard[i], 0, board[i].length);
			}
			node curNode=new node(r,c,0);
			for(int Goal:per) {
				curNode=BFS(Goal,tmpBoard,curNode);
				tmpBoard[curNode.x][curNode.y]=0;
				curNode=BFS(Goal,tmpBoard,curNode);
				tmpBoard[curNode.x][curNode.y]=0;
			}
			answer=Math.min(answer, curNode.cnt);
		}
		
		
		return answer;
	}
	
	private static node BFS(int goal, int[][] tmpBoard,node curNode) {
		que=new LinkedList<>();
		que.add(curNode);
		boolean[][] visit=new boolean[4][4];
		System.out.println(curNode.x+" "+curNode.y);
		visit[curNode.x][curNode.y]=true;
		while(!que.isEmpty()) {
			node cur=que.poll();
			if(tmpBoard[cur.x][cur.y]==goal)return new node(cur.x,cur.y,cur.cnt+1);
			for(int d=0;d<4;d++) {
				int dx=cur.x+dr[d];
				int dy=cur.y+dc[d];
				if(dx>=0&&dy>=0&&dx<4&&dy<4&&!visit[dx][dy]) {
					visit[dx][dy]=true;
					System.out.println(dx+" "+dy+" "+(cur.cnt+1));
					que.add(new node(dx,dy,cur.cnt+1));
				}
			}
			for(int d=0;d<4;d++) {
				node temp=crtl(cur.x,cur.y,d,tmpBoard);
				int dx=temp.x;
				int dy=temp.y;
				if((cur.x!=dx||cur.y!=dy)&&!visit[dx][dy]) {
					visit[dx][dy]=true;
					que.add(new node(dx,dy,cur.cnt+1));
					
				}
			}
		}

		return null;
	}
	private static node crtl(int x, int y, int d,int[][]tmpBoard) {
		x+=dr[d];
		y+=dc[d];
		while(x>=0&&y>=0&&x<4&&y<4) {
			if(tmpBoard[x][y]!=0) {
				return new node(x,y,0);
			}
			x+=dr[d];
			y+=dc[d];
		}
		return new node(x-dr[d],y-dc[d],0);
		
	}
	private static void permutation(int tmp, int idx) {
		if(idx==tmp) {
			int[] temp=new int[tmp];
			System.arraycopy(num, 0, temp,0, tmp);
			list.add(temp);
			return;
		}
		for(int i=1;i<=tmp;i++) {
			if(!check[i]) {
				check[i]=true;
				num[idx]=i;
				permutation(tmp, idx+1);
				check[i]=false;
			}
		}
		
	}

}