[2021 Kakao Blind] 카드 짝 맞추기 (Java)

허주환·2023년 2월 28일
0
post-thumbnail

2021 Kakao Blind - 카드 짝 맞추기
Level: 3
Language: Java
Comment: 순열(dfs), bfs, 시뮬
URL: https://programmers.co.kr/learn/courses/30/lessons/72415
전체 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/main/java/com/programmers/kakao2021/blind/Test6BFS.java
테스트 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/test/java/com/programmers/kakao2021/blind/Test6BFSTest.java

0. 문제 설명

  • 문제 URL 참고

1. 로직

I. 4x4 배열을 한번 쓱 훌틈

  • 0을 제외한 1 ~ 6 를 가진 카드 번호
  • 카드 번호를 Set<Integer> hs 에 저장
  • 카드 위치를 List<List<card>> points에 저장
    • points ex) [ [ {1번 카드, x1, y1}, {1번 카드, x2, y2} ], .. ]
List<List<Card>> points = new ArrayList<>();
Set<Integer> hs = new HashSet<>();
for (int i = 0; i <= 6; i++) points.add(new ArrayList<>());

for (int i = 0; i < board.length; i++) {
	for (int j = 0; j < board[i].length; j++) {
		int index = board[i][j];
		if (index > 0) {
			hs.add(index);
            points.get(index).add(new Card(i, j, 0));
        }
    }
}

II. 저장한 번호를 순열 알고리즘을 돌려카드 짝 맞추는 순서의 모든 경우의 수를 찾음

  • 짝 맞추는 순서 (1 --> 2 --> 3) int[]로 표현

    • ex1) 1 --> 2 --> 3 = [1, 2, 3]
    • ex2) 1 --> 3 --> 2 = [1, 3, 2]
    • exN) ...
  • 모든 경우의 수를 List<int[]> result 에 모두 저장

    • ex) [ [1, 2, 3], [1, 3, 2], ... ]
    • 구해진 카드 짝 맞추는 모든 순서로 게임을 진행해서 가장 작은 비용을 구해야함
  int n = hs.size();
  int[] arr = hash2Array(hs);
  int[] output = new int[n];
  List<int[]> result = new ArrayList<>();
  boolean[] visited = new boolean[n];
  Permutation.perm(arr, output, result, visited, 0, n, n);

III. 카드 짝 맞추는 순서대로 카드 번호 위치를 Queue<List<Card>>에 담아서 카드 짝 맞추기 시작

  • Queue는 카드 짝 맞추는 순서
  • List<Card>는 카드의 위치를 담고 있음 (항상 2개의 크기를 가짐)
  • Queue에 [1, 3, 2] 들어있다면
    • poll() 1회
      • get(0): 1번 카드의 위치 A (ax, ay)
      • get(1): 1번 카드의 위치 B (bx, by)
    • poll() 2회
      • get(0): 3번 카드의 위치 C (cx, cy)
      • get(1): 3번 카드의 위치 D (dx, dy)
    • poll() 3회
      • get(0): 2번 카드의 위치 E (ex, ey)
      • get(1): 2번 카드의 위치 F (fx, fy)
map = new int[4][4];
for (int[] indexList : result) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            map[i][j] = board[i][j];
        }
    }
    Queue<List<Card>> queue = new LinkedList<>();
    for (int index : indexList) queue.offer(points.get(index));

    int cost = gameStart(r, c, queue);
    answer = Math.min(answer, cost);
}

VI. 위치 확인

  • 위와 같이 [1, 3, 2] 순서대로 진행되면
  • 현재 위치가 두 개의 1번 카드 중에 있는지 확인
    • 1번 카드 위에 있다면
      • 두 개의 1번 카드 중에 어느 카드인지 확인하여 start, end를 정함
    • 1번 카드 위에 없다면
      • 두 개의 1번 카드 중에 어느 카드가 현재위치에서 가까운지 찾기
        • (현재위치), 1번 카드 위치 A - bfs 진행
        • (현재위치), 1번 카드 위치 B - bfs 진행
        • 현재위치에서 가까운 카드를 start, 먼 카드를 end로 지정
        • 위 bfs 중 최소 값을 cost에 비용 저장
  • 정해진 start, end - bfs 진행
  • bfs 진행 후 cost에 비용 저장, start, end 0 처리(뒤집어짐 처리)
  • 나머지 [3, 2] 도 동일 진행
int row = r;
int col = c;
int cost = 0;

while (!indexQueue.isEmpty()) {
    List<Card> cards = indexQueue.poll();
    int index = map[cards.get(0).row][cards.get(0).col];

    /*
    * 처음 위치가 순서에 맞는 카드면 바로 bfs
    * 처음 위치가 순서에 맞는 카드가 아니면 가까운 카드를 탐색 후 bfs
    * */
    Card start, end;
    if (map[row][col] == index) {
        int cardRow = cards.get(0).row;
        int cardCol = cards.get(0).col;
        if (row == cardRow && col == cardCol) {
            start = cards.get(0);
            end = cards.get(1);
        }
        else {
            start = cards.get(1);
            end = cards.get(0);
        }
    }
    else {
        Card current = new Card(row, col);
        int result1 = bfs(current, cards.get(0));
        int result2 = bfs(current, cards.get(1));
        if (result1 >= result2) {
            cost += result2;
            start = cards.get(1);
            end = cards.get(0);
        }
        else {
            cost += result1;
            start = cards.get(0);
            end = cards.get(1);
        }
    }
    /* enter 비용: +2 */
    cost += bfs(start, end) + 2;
    row = end.row;
    col = end.col;

    /* 뒤집기 */
    map[start.row][start.col] = 0;
    map[end.row][end.col] = 0;
}

V. BFS

Control 키를 누르면 여러칸을 움직일 수 있는 것 때문에
문제의 난이도(Level 3)보다 높은 느낌을 받았다...

  • 현재 위치(current)가 end의 위치이면 cost 에 비용 저장후 bfs 종료
  • 기본 bfs 진행(한 칸 위치 이동)
  • control 키를 입력해서 이동 가능한지 판단 (여러칸 위치 이동)
    • 카드 종류 (1 ~ 6)를 만나면 그 자리에서 멈춤
private static int bfs(Card start, Card end) {
    Queue<Card> queue = new LinkedList<>();
    int cost = 0;
    boolean[][] visited = new boolean[4][4];

    queue.add(start);
    while (!queue.isEmpty()) {
        Card current = queue.poll();

        /* enter !!*/
        if (current.row == end.row && current.col == end.col) {
            cost = current.cost;
            break;
        }

        /* 한칸 이동 */
        for (int[] dir : dirs) {
            int nRow = current.row + dir[0];
            int nCol = current.col + dir[1];
            if (canMove(nRow, nCol, visited)) {
                visited[current.row][current.col] = true;
                queue.offer(new Card(nRow, nCol, current.cost + 1));
            }
        }

        /* 여러칸 이동*/
        for (int[] dir : dirs) {
            int nRow = current.row;
            int nCol = current.col;
            while (canMove(nRow + dir[0], nCol + dir[1])) {
                nRow += dir[0];
                nCol += dir[1];

                if (!visited[nRow][nCol] && map[nRow][nCol] != 0) break;
            }

            if (canMove(nRow, nCol, visited)) {
                visited[current.row][current.col] = true;
                queue.offer(new Card(nRow, nCol, current.cost + 1));
            }
        }
    }

    return cost;
}

전체 코드

/*
 * @2021 kakao blind recruitment
 * @TestName: 카드 짝 맞추기
 * @URL: https://programmers.co.kr/learn/courses/30/lessons/72415
 * @COMMENT: 순열, bfs
 */
public class Test6BFS {

    static class Card {
        int row, col, cost;

        public Card(int row, int col) {
            this(row, col, 0);
        }

        public Card(int row, int col, int cost) {
            this.row = row;
            this.col = col;
            this.cost = cost;
        }

        @Override
        public String toString() {
            return "(" + row + ", " + col + ", " + cost + ')';
        }
    }

    static List<List<Card>> points;
    static int[][] map;
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public static int solution(int[][] board, int r, int c) {
        int answer = Integer.MAX_VALUE;
        points = new ArrayList<>();
        List<List<Card>> points = new ArrayList<>();
        Set<Integer> hs = new HashSet<>();
        for (int i = 0; i <= 6; i++) points.add(new ArrayList<>());
        // 순열 배열 만들기.
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                int index = board[i][j];
                if (index > 0) {
                    hs.add(index);
                    points.get(index).add(new Card(i, j, 0));
                }
            }
        }

        int n = hs.size();
        int[] arr = hash2Array(hs);
        int[] output = new int[n];
        List<int[]> result = new ArrayList<>();
        boolean[] visited = new boolean[n];
        Permutation.perm(arr, output, result, visited, 0, n, n);

        map = new int[4][4];
        for (int[] indexList : result) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    map[i][j] = board[i][j];
                }
            }
            Queue<List<Card>> queue = new LinkedList<>();
            for (int index : indexList) queue.offer(points.get(index));

            int cost = gameStart(r, c, queue);
            answer = Math.min(answer, cost);
        }

        return answer;
    }

    private static int gameStart(int r, int c, Queue<List<Card>> indexQueue) {
        int row = r;
        int col = c;
        int cost = 0;

        while (!indexQueue.isEmpty()) {
            List<Card> cards = indexQueue.poll();
            int index = map[cards.get(0).row][cards.get(0).col];

            /*
            * 처음 위치가 순서에 맞는 카드면 바로 bfs
            * 처음 위치가 순서에 맞는 카드가 아니면 가까운 카드를 탐색 후 bfs
            * */
            Card start, end;
            if (map[row][col] == index) {
                int cardRow = cards.get(0).row;
                int cardCol = cards.get(0).col;
                if (row == cardRow && col == cardCol) {
                    start = cards.get(0);
                    end = cards.get(1);
                }
                else {
                    start = cards.get(1);
                    end = cards.get(0);
                }
            }
            else {
                Card current = new Card(row, col);
                int result1 = bfs(current, cards.get(0));
                int result2 = bfs(current, cards.get(1));
                if (result1 >= result2) {
                    cost += result2;
                    start = cards.get(1);
                    end = cards.get(0);
                }
                else {
                    cost += result1;
                    start = cards.get(0);
                    end = cards.get(1);
                }
            }
            /* enter 비용: +2 */
            cost += bfs(start, end) + 2;
            row = end.row;
            col = end.col;

            /* 뒤집기 */
            map[start.row][start.col] = 0;
            map[end.row][end.col] = 0;
        }

        return cost;
    }

    private static int bfs(Card start, Card end) {
        Queue<Card> queue = new LinkedList<>();
        int cost = 0;
        boolean[][] visited = new boolean[4][4];

        queue.add(start);
        while (!queue.isEmpty()) {
            Card current = queue.poll();

            /* enter !!*/
            if (current.row == end.row && current.col == end.col) {
                cost = current.cost;
                break;
            }

            /* 한칸 이동 */
            for (int[] dir : dirs) {
                int nRow = current.row + dir[0];
                int nCol = current.col + dir[1];
                if (canMove(nRow, nCol, visited)) {
                    visited[current.row][current.col] = true;
                    queue.offer(new Card(nRow, nCol, current.cost + 1));
                }
            }

            /* 여러칸 이동 */
            for (int[] dir : dirs) {
                int nRow = current.row;
                int nCol = current.col;
                while (canMove(nRow + dir[0], nCol + dir[1])) {
                    nRow += dir[0];
                    nCol += dir[1];

                    if (!visited[nRow][nCol] && map[nRow][nCol] != 0) break;
                }

                if (canMove(nRow, nCol, visited)) {
                    visited[current.row][current.col] = true;
                    queue.offer(new Card(nRow, nCol, current.cost + 1));
                }
            }
        }

        return cost;
    }

    /*
    * array 범위에 맞는지, 방문을 했는지 체크
    * */
    private static boolean canMove(int movedRow, int movedCol, boolean[][] visited) {
        return canMove(movedRow, movedCol)&& !visited[movedRow][movedCol];
    }

    /*
     * array 범위에 맞는지
     * */
    private static boolean canMove(int movedRow, int movedCol) {
        return movedRow >= 0 && movedRow < map.length
                && movedCol >= 0 && movedCol < map[0].length;
    }

    private static int[] hash2Array(Set<Integer> set) {
        return set.stream()
                .mapToInt(Integer::valueOf)
                .toArray();
    }
}

후기

여러칸을 움직이는 규칙이 있어 어려움이 있었다. (이 부분만 다른 분들의 코드를 보며 연구함...)
이것 때문에 난이도는 Level 3.5 이상은 되는것 같은 느낌을 받았다.
처음에 int[][] map을 bfs 할 때마다 초기화 시켜줘서 반 이상의 TC가 틀려 삽질을좀 했다.
카드 방문 순서를 다 완료 한 후에 초기화를 해줘서 해결했다.
아직 Level 3 이상의 문제들은 어렵다...

profile
Junior BE Developer

0개의 댓글