[프로그래머스/자바] 카드 짝 맞추기 풀이 - 2021 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2021 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

 

접근 -> 브루트포스, DFS, BFS

 

 

카드를 뽑는 순서의 모든 경우를 DFS로 완전탐색한다.

map에 key를 카드번호로, value에는 카드 두개의 위치가 저장되어 있는 [2][2] 크기의 2차원 배열로 담는다.

그리고 DFS를 통해 map에 저장된 카드 위치를 순서대로, 순서 반대로 한번씩 수행한다.

 

카드의 갯수만큼 DFS로 뽑았다면, 

뽑은 카드로 BFS를 돌려 키 조작 횟수의 최솟값을 찾는다.

 

목적지 하나에 도달할 때마다 BFS의 시작점을 도달한 카드로 지정하고, 다시 목적지를 도달할 때까지 BFS를 진행한다.

즉, for문으로 카드의 갯수만큼 BFS를 진행하는 것이다.

 

예를 들어 (0,1) (2,3) (2,2) (0,0) 으로 카드를 뽑았다면

먼저 (0,1) 시작점으로 지정한다. 그리고 그 다음 목적지인 (2,3)를 만날 때까지 BFS를 진행한다.

(2,3)에 도달했다면 그 카드를 시작점으로 지정한 후 (2,2)을 만날 때까지 BFS를 진행하고,

마지막 카드까지 이 과정을 반복한다.

 

 

주의할점

< [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다. 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다. >

문제에서 위 조건을 구현하는게 가장 까다로운 것 같다.

- 만약 카드를 만났다면 그 다음으로는 ctrl을 눌러 더이상 갈 수 없다. 

그리고 카드를 아예 만나지 못했다면 가장 끝으로 이동한다.

카드를 만났는지, 만나지 않았는지를 확인하기 위해 boolean flag 변수를 사용했다.

 

- BFS가 진행될 때마다 카드가 뒤집히는 것(카드가 없어짐)이므로

목적지 카드에 도달할 때마다 해당 카드 위치의 board를 0으로 바꿔야 한다.

 

- 처음에는 ctrl없이 방향키로 한칸 이동했을 때의 위치를 이미 방문했다면,

ctrl으로도 아예 이동하지 않는 걸로 구현했었는데 7,11,19,22,27,30 테케에서 틀렸다.

이처럼 구현하는 경우 반례는 아래와 같다.

0	0	1	1
0	0	1	0
0	0	1	1
0	0	0	0

만약 위 표처럼 visit가 구성되어 있고 현재 위치가 [0][3], 목적지가 [0][0]이라면

[0][3]에서 ctrl을 눌러서 바로 [0][0]으로 이동할 수 있다. ( 중간에 카드가 없다고 가정 )

하지만 [0][2]의 visit이 이미 true이므로 [0][0], [0][1]으로 이동하지 않고 끝나버린다.

즉, 방향키로만 한칸 이동했을 때의 visit와 상관없이

ctrl으로 갈 수 있는지도 고려해줘야 한다.

 

 

 

 

 

배운점 및 느낀점

문제를 완벽히 이해한 것 같았는데 막상 풀어보니까 아니었다.

문제의 조건을 정확히 구현하고, 틀린 테케가 있을 때 빠르게 반례를 찾아내 디버깅하는 것.. 너무 어렵다.

그리고 DFS를 통해 카드를 뽑는 모든 경우의 수를 고려하는 것도 다른 분 풀이를 참고했다.

언제쯤 어려운 문제를 혼자 구현해낼 수 있을지..

그래도 그 외에는 혼자 해결해서 뿌듯하다. 물론 시간이 너무 오래걸렸지만 ㅎ

카카오 기출은 일단 1~3 Level만 풀고 있는데, 풀어본 문제 중 가장 어려웠다.

이 정도면 Level 4 아닌가 싶다..

 

 

import java.util.*;

class Solution {
	static int[][] move = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
	static HashMap<Integer, int[][]> map = new HashMap<>();
	static int min = Integer.MAX_VALUE;
	static int n = 0;
	static int[][] card;
	static boolean[] visit;
	static boolean[][] bfs_visit;
	static int R, C;
	static int board_len;
	static int[][] new_board;
    
    public int solution(int[][] board, int r, int c) {
		R = r; C = c;
		new_board = board;
		board_len = board.length;

		// key는 카드 번호, value는 카드 위치 두개.
		for(int i=0;i<board.length;i++)
			for(int j=0;j<board[0].length;j++) 
				if(board[i][j] != 0) {
					if(!map.containsKey(board[i][j])) {
						int[][] temp = new int[2][2];
						temp[0][1] = i; temp[0][0] = j;
						map.put(board[i][j], temp);
						n++;
					}
					else {
						int[][] temp = map.get(board[i][j]);
						temp[1][1] = i; temp[1][0] = j;
					}
				}

		card = new int[n * 2][2];
		visit = new boolean[n + 1];

		DFS(0);

		return min;
	}

	static void DFS(int depth) {
		// 카드갯수만큼 배열에 담았으면 BFS로 최솟값 찾기
		if(depth == n) { 
			min = Math.min(BFS(), min);
			return;
		}

		for(int i=1;i<=n;i++) {
			if(!visit[i] && map.containsKey(i)) {
				visit[i] = true;
				int pos[][] = map.get(i);
				int idx = depth * 2;
				card[idx] = pos[0]; card[idx + 1] = pos[1];
				DFS(depth + 1);

				// 같은 번호의 카드 뽑는 순서 반대로
				card[idx] = pos[1]; card[idx + 1] = pos[0];
				DFS(depth + 1);
				visit[i] = false;
			}
		}

	}

	static int BFS() {
		Queue<Point> q = new LinkedList<>();
		int[][] tmp_board = new int[board_len][board_len];
		for(int i=0;i<board_len;i++)
			tmp_board[i] = new_board[i].clone();

		int cnt = 0;
		int startX = R;
		int startY = C;

		// start 부터 card의 원소까지
		for(int i=0;i<card.length;i++) {
			bfs_visit = new boolean[board_len][board_len];
			q.clear();
			q.offer(new Point(startX, startY, 0));

			while(!q.isEmpty()) {
				Point now = q.poll();

				if(card[i][1] == now.x && card[i][0] == now.y) {
					startX = now.x;
					startY = now.y;
					cnt += now.cnt + 1;
					tmp_board[now.x][now.y] = 0;
					break;
				}

				for(int j=0;j<4;j++) {
					int nextX = now.x + move[j][1];
					int nextY = now.y + move[j][0];

					// 방향키만 누르는 경우
					if(check(nextX, nextY) && !bfs_visit[nextX][nextY]) {
						bfs_visit[nextX][nextY] = true;
						q.offer(new Point(nextX, nextY, now.cnt + 1));
					}

					if(check(nextX, nextY) && tmp_board[nextX][nextY] == 0) {
						// 방향키랑 ctrl 키를 같이 누르는 경우
						boolean flag = false;
						for(int k=1;k<=board_len - 2;k++) {
							int newX = nextX, newY = nextY;

							if(move[j][1] != 0) 
								newX += move[j][1] < 0 ? -k : k;
							else 
								newY += move[j][0] < 0 ? -k : k;
							
							if(!flag && check(newX, newY) && !bfs_visit[newX][newY] && tmp_board[newX][newY] != 0) {
								bfs_visit[newX][newY] = true;
								q.offer(new Point(newX, newY, now.cnt + 1));
								flag = true;
							}
						}

						// 해당 방향에 카드가 하나도 없다면 그 방향의 마지막 칸으로 이동
						if(!flag) {
							int newX = nextX, newY = nextY;
							
							if(move[j][1] != 0)
								newX = move[j][1] > 0 ? board_len - 1 : 0;
							else 
								newY = move[j][0] > 0 ? board_len - 1 : 0;
								
							if(check(newX, newY) && !bfs_visit[newX][newY]) {
								bfs_visit[newX][newY] = true;
								q.offer(new Point(newX, newY, now.cnt + 1));
								flag = true;
							}
						}
					}

				}
			}

		}

		return cnt;
	}

	static boolean check(int x, int y) {
		if(x < 0 || x >= board_len || y < 0 || y >= board_len)
			return false;

		return true;
	}

	static class Point {
		int x, y, cnt;

		Point(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}

}