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

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

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

 

- 참고 링크 : https://www.youtube.com/watch?v=aZfzE4jIIMU 

 

- 풀이

 : 너무 못해서 (3일 이상 이 문제에만 쏟았는데 실패..) 결국 답 해석 해주는 유튜브를 찾아서 보면서 끄덕끄덕 하면서 풀었다.

 : BFS + 순열의 재귀적 활용 (응용) 문제 라고 생각한다.
 : 순열이 나오면 항상 약한데 이를 보완해야겠다.

- 참고 정답 코드

 

 

- 실패 코드

 : 모수가 적다는 것은 인지하고 있었는데 permutation 을 이용한 방법 찾기는 정말 생각도 못했다.
 : 좀 더 생각의 폭을 넓힐 수 있어서 좋았다.

import java.util.*;

class Solution {
    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{-1, 1, 0, 0};
    
    public int solution(int[][] board, int r, int c) {
        int count = 0;
        int sNum = board[r][c];
        
        if (sNum == 0) {
            // 제일 가까운 포인트 찾기
            Point sp = findStartPoint(board, r, c);
            // System.out.println(sp.x + " " + sp.y);
            count += getFastestStep(board, r, c, sp.x, sp.y);
            r = sp.x;
            c = sp.y;
            sNum = board[r][c];
        }
        
        Point np = findNextPoint(board, r, c, sNum);
        System.out.println(np.x + " " + np.y);
        count += getFastestStep(board, r, c, np.x, np.y);
        System.out.println(count);
        r = np.x;
        c = np.y;
        
        // 1 ~ 3
        processGame(board, r, c);
        
        return count;
    }
    
    public Point findStartPoint(int[][] board, int r, int c) {
        int count = 0;
        
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c, 0, 0));
        
        while (!q.isEmpty()) {
            Point cp = q.poll();
            int cx = cp.x;
            int cy = cp.y;
            int cDir = cp.dir;
            int cCount = cp.count;
            
            if (board[cx][cy] > 0) {
                return new Point(cx, cy, 0, 0);
            }
            
            for (int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                int nDir = i;
                if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
                    if (cDir != nDir) {
                        cCount++;
                    }
                    q.add(new Point(nx, ny, i, cCount));
                }
            }
        }
        
        return null;
    }
    
    public Point findNextPoint(int[][] board, int r, int c, int targetNum) {
        int count = 0;
        
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c, 0, 0));
        
        while (!q.isEmpty()) {
            Point cp = q.poll();
            int cx = cp.x;
            int cy = cp.y;
            int cDir = cp.dir;
            int cCount = cp.count;
            
            if (r != cx && c != cy && board[cx][cy] == targetNum) {
                return new Point(cx, cy, 0, 0);
            }
            
            for (int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                int nDir = i;
                if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
                    if (cDir != nDir) {
                        cCount++;
                    }
                    q.add(new Point(nx, ny, i, cCount));
                }
            }
        }
        
        return null;
    }
    
    public int getFastestStep(int[][] board, int r, int c, int x, int y) {
        int count = 0;
        int start = board[x][y];
        if (r == x && c == y) {
            return count;
        }
        
        count = 1;
        boolean[][] visited = new boolean[4][4];
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(r, c, 0, count));
        
        while (!q.isEmpty()) {
            Point cp = q.poll();
            int cx = cp.x;
            int cy = cp.y;
            int cDir = cp.dir;
            int cCount = cp.count;
            
            visited[cx][cy] = true;
            // System.out.println("gdgd " + cx + " " + cy);
            
            if (r != cx && c != cy && start == board[cx][cy]) {
                // System.out.println("gdgd " + cx + " " + cy);
                count = cCount+1;
                break;
            }
            
            for (int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                int nDir = i;
                if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && (board[nx][ny] == 0 || board[nx][ny] == start)) {
                    if (!visited[nx][ny]) {
                        if (cDir != nDir) {
                            cCount++;
                        }
                        q.add(new Point(nx, ny, i, cCount));   
                    }
                }
            }
        }
        
        return count;
    }
    
    public void processGame(int[][] board, int x, int y) {
        int sNum = board[x][y];
    }
}

class Point {
    int x;
    int y;
    int dir;
    int count;
    
    public Point(int x, int y, int dir, int count) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.count = count;
    }
}

 

- 실패 코드 2

 : ctrl + -> 의 경우의 수를 잘못 파악했다. 방향만 바꾸지 않으면 한번에 다 갈 수 있다고 생각했는데 못 가는 경우가 있다. 

 

import java.util.*;

class Solution {
    private int[][] arr = {{1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}};
    private int[] dx = new int[]{0, 0, -1, 1};
    private int[] dy = new int[]{-1, 1, 0, 0};
    private int[][] board;
    private boolean[][] visited;
    
    public int solution(int[][] board, int r, int c) {
        int answer = 0;
        int minCount = 0;
        int cx = r;
        int cy = c;
        
        for (int i=0; i< arr.length; i++) {
            this.board = getCopyBoard(board);
            int curCount = 0;
            
            boolean isCountable = true;
            for (int j=0; j<3; j++) {
                // printBoard(this.board);
                int[] cards = arr[i];
                int startCard = cards[j];
                System.out.println("r : " + r + " c : " + c + " startCard : " + startCard);
                Point sp = findPoint(cx, cy, startCard);
                System.out.println("x : " + sp.x + " y : " + sp.y + " count : " + sp.count);
                curCount += sp.count;

                cx = sp.x;
                cy = sp.y;
                
                int targetCard = this.board[cx][cy];
                this.board[cx][cy] = 0;
                Point tp = findPoint(cx, cy, targetCard);
                if (tp != null) {
                    cx = tp.x;
                    cy = tp.y;
                    this.board[cx][cy] = 0;
                    System.out.println("tx : " + tp.x + " ty : " + tp.y + " count : " + (tp.count + 2));
                    curCount += tp.count + 2; // 시작 끝 엔터 2번
                } else {
                    isCountable = false;
                    break;
                }
                
                System.out.println("----------");
            }
            
            if (isCountable) {
                System.out.println("curCount : " + curCount);   
            }

            System.out.println("<끝> ");
        }
        return answer;
    }
    
    public int[][] getCopyBoard(int[][] board) {
        int[][] copyBoard = new int[board.length][board[0].length];
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
                // System.out.print(board[i][j] + " ");
                copyBoard[i][j] = board[i][j];
            }
            // System.out.println(" ");
        }
        return copyBoard;
    }
    
    public Point findPoint(int cx, int cy, int card) {
        System.out.println("fp : " + card);
        Point cp = new Point(cx, cy, -1, 0);
        this.visited = new boolean[4][4];
        if (this.board[cx][cy] == card) {
            return cp;
        }
        
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(cx, cy, -1, 1));
        
        Point rp = null;
        while (!q.isEmpty()) {
            Point np = q.poll();
            
            if (board[np.x][np.y] == card) {
                rp = np;
                break;
            }
            
            visited[np.x][np.y] = true;
            
            for (int i=0; i<4; i++) {
                int nx = np.x + dx[i];
                int ny = np.y + dy[i];
                if (isValidPoint(nx, ny) && !visited[nx][ny] && (board[nx][ny] == 0 || board[nx][ny] == card)) {
                    int nCount = np.count;
                    if (np.dir != -1 && np.dir != i) {
                        nCount += 1;
                    }
                    q.add(new Point(nx, ny, i, nCount));
                }
            }
        }
        
        return rp;
    }
    
    public boolean isValidPoint(int x, int y) {
        return x >= 0 && x < 4 && y >= 0 && y < 4;
    }
    
    public void printBoard(int[][] board) {
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board[0].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println(" ");
        }
    }
    
    public void printVisited(boolean[][] visited) {
        for (int i=0; i<visited.length; i++) {
            for (int j=0; j<visited[0].length; j++) {
                System.out.print(visited[i][j] + " ");
            }
            System.out.println(" ");
        }
    }
}

class Point {
    int x;
    int y;
    int dir;
    int count;
    
    public Point(int x, int y, int dir, int count) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.count = count;
    }
}