Java - [프로그래머스]72415 - Lv3.카드 짝 맞추기

출처

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

프로그래머스

 

문제

 

이 문제는 짝이 맞는 카드를 뒤집어 모두 없어질때 까지 반복하는데, 가장 최소로 조작했을때의 횟수를 구하는 문제이다.

 

풀이

이 문제는 어떤 카드를 먼저 뒤집어야 최소의 횟수가 되는지 알 수 없기 때문에 모든 순서에 대해 탐색을 진행하여야 한다. 따라서 DFS를 이용하여 순열을 만들어 완전 탐색을 진행한다. 또한 카드를 맞추기 위해 해당 카드로 이동하는 최단 경로를 구하기 위해 BFS도 사용하였다.

 

• DFS(현재 커서의 위치, 현재 depth, 현재까지의 횟수)
  • visited를 이용해 방문여부를 체크하며 순열을 만들어 탐색을 진행한다
  •  한 번호의 카드는 총 두개가 존재한다. 따라서 아래 두가지 경우 중 적은 횟수로 탐색을 수행한다. 이때, 카드의 두가지 위치는 Map에 저장해두었다.
  • [시작점 -> 1번카드 -> 2번카드  / 시작점 -> 2번카드 -> 1번카드] + (Enter를 누르는것을 고려하여 + 2)
• BFS(출발점, 도착점)
  • 이 함수에서는 일반 dx, dy로 상하좌우로 이동하는 것 뿐만 아니라, ctrl 이동도 고려하여 탐색을 진행해주어야 한다.
  • BFS는 항상 최단경로로 이동하므로, 도착하면 그 때의 이동 횟수를 반환한다.

 

코드

import java.util.*;

import java.util.*;

class pgs72415 {
    public int[][] board;
    public Map<Integer, List<Node>> map;
    public int answer, cardCnt;
    public boolean[] visitedCard;

    public int[] dx = {1, 0, -1, 0};
    public int[] dy = {0, 1, 0 , -1};

    public int solution(int[][] board, int r, int c) {
        this.board = board;
        cardCnt = 0;
        answer = Integer.MAX_VALUE;
        map = new HashMap<>();

        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])) {
                        map.get(board[i][j]).add(new Node(i, j, 0));
                    } else {
                        map.put(board[i][j], new ArrayList<>());
                        map.get(board[i][j]).add(new Node(i, j, 0));
                        cardCnt++;
                    }
                }
            }
        }
        visitedCard = new boolean[cardCnt + 1];
        dfs(new Node(r, c, 0), 0, 0);

        return answer;

    }

    public void dfs(Node now, int depth, int nowCnt) {
        if (depth == cardCnt) {
            answer = Math.min(answer, nowCnt);
            return;
        }

        for (int i = 1; i <= cardCnt; i++) {
            if (!visitedCard[i]) {
                List<Node> list = map.get(i);
                Node node1 = list.get(0);
                Node node2 = list.get(1);

                int dir1 = move(now, node1) + move(node1, node2) + 2;
                int dir2 = move(now, node2) + move(node2, node1) + 2;

                board[node1.x][node1.y] = 0;
                board[node2.x][node2.y] = 0;
                visitedCard[i] = true;
                if (dir1 > dir2) {
                    dfs(node1, depth + 1, nowCnt + dir2);
                } else {
                    dfs(node2, depth + 1, nowCnt + dir1);
                }

                board[node1.x][node1.y] = i;
                board[node2.x][node2.y] = i;
                visitedCard[i] = false;
            }
        }

    }

    public int move(Node start, Node dest) {
        Deque<Node> dq = new ArrayDeque<>();
        boolean[][] visited = new boolean[board.length][board[0].length];
        visited[start.x][start.y] = true;
        dq.add(start);

        while (!dq.isEmpty()) {
            Node now = dq.remove();

            if (now.x == dest.x && now.y == dest.y) {
                return now.cnt;
            }

            // 일반 이동
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (isRange(nx, ny) && !visited[nx][ny]) {
                    dq.add(new Node(nx, ny, now.cnt + 1));
                    visited[nx][ny] = true;
                }
            }

            // ctrl 이동
            for (int i = 0; i < 4; i++) {
                int nx = now.x;
                int ny = now.y;


                while (true) {
                    nx += dx[i];
                    ny += dy[i];
                    if (!isRange(nx, ny)) {
                        nx -= dx[i];
                        ny -= dy[i];
                        break;
                    }
                    if (board[nx][ny] != 0) {
                        break;
                    }
                }
                if (visited[nx][ny]) continue;
                dq.add(new Node(nx, ny, now.cnt + 1));
                visited[nx][ny] = true;
            }
        }
        return -1;
    }


    public boolean isRange(int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

    public class Node{
        int x;
        int y;
        int cnt;

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