[2021 KAKAO BLIND RECRUITMENT] 카드 짝 맞추기

[uijin-j]

🔗 카드 짝 맞추기

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include #include using namespace std; vector> board; vector card; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int answer = 0x3f3f3f3f; int r,c; int bfs(int dest){ bool check[4][4] = {0, }; queue,int>> q; q.push({{r,c},0}); check[r][c] = true; while(!q.empty()){ int x = q.front().first.first; int y = q.front().first.second; int cnt = q.front().second; q.pop(); if(board[x][y] == dest){ board[x][y] = 0; r = x, c = y; return cnt+1; } for(int i=0;i<4;i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4) continue; if(!check[nx][ny]){ check[nx][ny] = true; q.push({{nx,ny},cnt+1}); } } for(int i=0;i<4;i++){ int nx = x; int ny = y; while(nx+dx[i]>=0&&ny+dy[i]>=0&&nx+dx[i]<4&&ny+dy[i]<4){ nx += dx[i]; ny += dy[i]; if(board[nx][ny]) break; } if(!check[nx][ny]){ check[nx][ny] = true; q.push({{nx,ny},cnt+1}); } } } } int solution(vector> b, int rr, int cc) { bool card_check[7] = {0,}; int depth =0; for(int i=0;i

코멘트

- 순열 + bfs까지는 접근했는데 문제를 이해를 못해서 답을 봤습니다. 1칸식 이동 or 숫자가 있는 칸까지 한 번에 이동이 아니라 무조건 후자인줄 알고 bfs구현을 못하겠다라고요.
- 그리고 여러가지 풀이를 봤는데 제가 참고한 풀이 같은 n을 방문할 차례일때 무조건 가까운 n을 먼저 방문하더라고요. 증명을 해보거나 찾아보려고 했는데 못찾았습니다. 카카오 풀이에서도  이렇게 말했는데 해당풀이는 무조건 가까운 다음 숫자를 먼저 방문하고 페어를 지워줍니다... 어떻게 가능한 걸까요...?

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.util.*; // 22:03 START! 23:30 STOP! (1시간 30분) // 17:22 RESTART! 17:58 END! (35분) class Solution { /** * 1. 각 카드를 뽑는 순서를 정한다. 최대 8개 O(8! * 2^8) * 2. 순서대로 카드를 뽑는다. (최소한의 움직임으로!) * 참고) 엔터 입력은 카드 수만큼 한다. */ int[][] board; int[] start; HashMap> map = new HashMap<>(); // map.get(i)는 i 캐릭터가 있는 좌표 리스트 int numOfPair = 0; // 카드 쌍의 수 boolean[] check = new boolean[9]; // dfs를 위해 필요한 배열 int min = Integer.MAX_VALUE; public int solution(int[][] board, int r, int c) { this.board = board; start = new int[]{r, c}; for(int i = 0; i < 4; ++i) { for(int j = 0; j < 4; ++j) { if(board[i][j] > 0) { // 캐릭터 발견! int num = board[i][j]; map.putIfAbsent(num, new ArrayList<>()); map.get(num).add(new int[]{i, j}); } } } numOfPair = map.size(); Deque stack = new ArrayDeque<>(); play(0, stack); return min; } public void play(int level, Deque stack) { if(level == numOfPair) { int[] point = new int[]{start[0], start[1]}; int[][] copy = copyArray(board); int total = 0; for(int[] target : stack) { int count = go(point, target, copy); total += count + 1; // Enter 연산까지 더하기 point = new int[]{target[0], target[1]}; copy[target[0]][target[1]] = 0; } min = Math.min(min, total); return; } for(int num : map.keySet()) { if(!check[num]) { check[num] = true; for(int i = 0; i < 2; ++i) { stack.push(map.get(num).get(i)); // push가 아니라 add를 해서 엄청 헤맸다..😢 stack.push(map.get(num).get((i + 1) % 2)); play(level + 1, stack); stack.pop(); stack.pop(); } check[num] = false; } } } int[] dx = {-1, 0, 1, 0}; int[] dy = {0, 1, 0, -1}; // point에서 target으로 가는 최단거리 public int go(int[] point, int[] target, int[][] board) { Queue q = new LinkedList<>(); q.offer(new Node(point[0], point[1], 0)); while(!q.isEmpty()) { Node node = q.poll(); if(node.x == target[0] && node.y == target[1]) { return node.count; } for(int d = 0; d < 4; ++d) { int nx = node.x + dx[d]; int ny = node.y + dy[d]; if(nx >= 0 && nx < 4 && ny >= 0 && ny < 4) { q.offer(new Node(nx, ny, node.count + 1)); } // ctrl int[] next = ctrl(d, node.x, node.y, board); q.offer(new Node(next[0], next[1], node.count + 1)); } } return -1; } public int[] ctrl(int d, int x, int y, int[][] board) { int nx = x + dx[d]; int ny = y + dy[d]; while(nx >= 0 && nx < 4 && ny >= 0 && ny < 4) { if(board[nx][ny] > 0) return new int[]{nx, ny}; nx += dx[d]; ny += dy[d]; } nx -= dx[d]; ny -= dy[d]; return new int[]{nx, ny}; } public class Node { int x, y, count; public Node(int x, int y, int count) { this.x = x; this.y = y; this.count = count; } } public int[][] copyArray(int[][] board) { int[][] result = new int[4][4]; for(int i = 0; i < 4; ++i) { for(int j = 0; j < 4; ++j) { result[i][j] = board[i][j]; } } return result; } } ```

코멘트

- 문제유형(백트레킹)을 떠올리는건 어렵지 않았는데, 구현하는 과정에서 실수가 많았던 것 같습니다😢