[프로그래머스] 카드 짝 맞추기(java)

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

프로그래머스

 

dfs와 bfs를 활용하는 문제이다. 난이도 자체가 어렵기보다는 빡코딩이라 실수하기 쉽다.

 

핵심

카드를 뒤집는 순서에 따라 카운팅이 달라지게 된다. 따라서 dfs를 통해 모든 순열을 탐색해 여한다.

중요한 점은 같은 종류의 카드가 2개가 있기 때문에 이를 어떤 카드를 먼저 뒤집느냐도 중요하다. -> 뒤집은 이후에 해당 위치가 달라지기 때문임. 이후 최단거리의 합들을 모두 더하면 된다.

 

정답 코드

import java.util.*;

class Solution {

    private int count = 0;
    private int result = Integer.MAX_VALUE;
    private boolean[] visited = new boolean[7];
    private Point[][] cardIndex = new Point[7][2];
    private int[][] map;
    private int[] dy = {1, -1, 0, 0};
    private int[] dx = {0, 0, 1, -1};

    public int solution(int[][] board, int r, int c) {
        map = board;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (map[i][j] == 0) {
                    continue;
                }
                if (!visited[map[i][j]]) {
                    visited[map[i][j]] = true;
                    count++;
                    cardIndex[map[i][j]][0] = new Point(i, j, 0);
                } else {
                    cardIndex[map[i][j]][1] = new Point(i, j, 0);
                }
            }
        }

        dfs(0, 0, r, c);
        return result;
    }

    public void dfs(int index, int sum, int nowX, int nowY) {
        if (index == count) {
            result = Math.min(result, sum);
            return;
        }

        for (int i = 1; i <= 6; i++) {
            if (!visited[i]) {
                continue;
            }
            int firstCount = bfs(nowX, nowY, cardIndex[i][0].x, cardIndex[i][0].y)
                    + bfs(cardIndex[i][0].x, cardIndex[i][0].y, cardIndex[i][1].x, cardIndex[i][1].y) + 2;

            int secondCount = bfs(nowX, nowY, cardIndex[i][1].x, cardIndex[i][1].y)
                    + bfs(cardIndex[i][1].x, cardIndex[i][1].y, cardIndex[i][0].x, cardIndex[i][0].y) + 2;

            visited[i] = false;
            map[cardIndex[i][0].x][cardIndex[i][0].y] = 0;
            map[cardIndex[i][1].x][cardIndex[i][1].y] = 0;

            if (firstCount < secondCount) {
                dfs(index + 1, sum + firstCount, cardIndex[i][1].x, cardIndex[i][1].y);
            } else {
                dfs(index + 1, sum + secondCount, cardIndex[i][0].x, cardIndex[i][0].y);
            }

            map[cardIndex[i][0].x][cardIndex[i][0].y] = i;
            map[cardIndex[i][1].x][cardIndex[i][1].y] = i;
            visited[i] = true;
        }
    }

    public int bfs(int sx, int sy, int tx, int ty) {
        Queue<Point> q = new LinkedList<>();
        boolean[][] check = new boolean[4][4];
        q.add(new Point(sx, sy, 0));
        check[sx][sy] = true;

        while (!q.isEmpty()) {
            Point now = q.poll();
            if (now.x == tx && now.y == ty) {
                return now.t;
            }

            for (int d = 0; d < 4; d++) {
                int moveX = now.x + dx[d];
                int moveY = now.y + dy[d];
                if (moveX < 0 || moveY < 0 || moveX >= 4 || moveY >= 4 || check[moveX][moveY]) {
                    continue;
                }
                check[moveX][moveY] = true;
                q.add(new Point(moveX, moveY, now.t + 1));
            }

            for (int d = 0; d < 4; d++) {
                int moveX = now.x;
                int moveY = now.y;
                while (true) {
                    moveX += dx[d];
                    moveY += dy[d];
                    if (moveX == 4 || moveY == 4 || moveX == -1 || moveY == -1) {
                        moveX -= dx[d];
                        moveY -= dy[d];
                        break;
                    }
                    if (map[moveX][moveY] != 0) {
                        break;
                    }
                }
                if (check[moveX][moveY]) {
                    continue;
                }
                check[moveX][moveY] = true;
                q.add(new Point(moveX, moveY, now.t + 1));
            }
        }
        return -1;
    }
}

class Point {
    int x, y, t;

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

 

해설

우선 카드의 종류와 위치를 카운팅 한다. 이는 배열을 사용하여 이후에 사용하기 쉬웠다.

이제 dfs를 통해 순열을 정하고 그 값대로 bfs를 진행한다.

순열을 통해 만약 카드가 3개라면 (1,2,3), (1,3,2), (2,1,3)... 이런 식으로 고를 수 있게 해 준다.

이제 어떤 카드를 먼저 골랐을 때 값이 더 적은 것을 선택한다.

bfs는 흔히 알고 있는 정석적으로 사용하였다.

다만 새로운 규칙인 일직선으로 쭉 이동하는 경우로 구현해 주었다.

 

 

배운 점

문제 자체는 어렵지 않다고 생각한다.

다만 처음 문제를 풀었을 때 bfs를 한 번에 시도하려 했다가 실수를 하고 이를 디버깅하는데 고생했다.

이후 이를 조금 더 분리하여 논리적으로 접근하여 풀 수 있었다.

오랜만에 프로그래머스 문제를 푸는데 역시 재미있는 것 같다.