카드 짝 맞추기 : https://programmers.co.kr/learn/courses/30/lessons/72415
Problem
Solve
특별한 알고리즘 없이 수열을 이용하여 카드를 방문하는 모든 경우의 수의 순서를 만들어 BFS를 통해 풀어내는 방법.
board의 크기가 4*4이고 카드의 종류가 최대 6개 이므로 모든 경우의 수를 다 확인할 수 문제이다.
문제 풀이 순서는 아래와 같다.
- 해당 board에 존재하는 카드 종류를 찾아내 카드를 방문하는 모든 경우의 수를 구한다.
- 각 경우의 수에서 방문해야할 카드를 찾는 최소한의 이동을 구하는 BFS(findCard)
- 찾은 카드의 위치에서 동일한 카드 종류를 찾는 최소한의 이동을 구하는 BFS(findPair)
- 2번,3번을 통해 구한 최소한의 이동 중 가장 작은 값을 반환한다.
(문제에서 그림 설명이 친절하게 나와있기 때문에 그림은 생략.)
코드의 양이 꽤나 많아서 설명을 자세하게 하겠다.
Code
import java.util.*;
class Solution {
int cardCount;
int[] dy = {-1,0,1,0};
int[] dx = {0,-1,0,1};
public int solution(int[][] board, int r, int c) {
//카드의 종류
HashSet<Integer> cardSet = getCardSet(board);
//카드의 종류를 넣어놓은 배열
int[] cardArr = new int[cardSet.size()];
int idx = 0;
for (int card : cardSet) {
cardArr[idx] = card;
idx++;
}
//카드의 방문 순서를 String으로 한 방문 리스트
List<String> orders = new ArrayList<>();
setOrders(cardArr, 0, "", orders);
int answer = Integer.MAX_VALUE;
//각 카드 방문에 대한 최소 거리 구하기
for (String order : orders) {
//시작 커서
Cursor cursor = new Cursor(c,r,0);
//카드 두짝을 모두 찾았을때 카드를 삭제 시키기 때문에 필요함
int[][] copyBoard = copyBoard(board);
for (char num : order.toCharArray()) {
//찾고자하는 카드를 찾았을때의 좌표와 거리 반환
cursor = findCard(num - '0', cursor.x, cursor.y, cursor.count, copyBoard);
//enter
cursor.count += 1;
//찾은 카드의 짝을 찾았을 때의 좌표와 거리 반환
cursor = findPair(num - '0', cursor.x, cursor.y, cursor.count,copyBoard);
//enter
cursor.count += 1;
}
//해당 카드방문 순서를 마쳤을때 다른 최소 거리와 비교
answer = Math.min(cursor.count, answer);
}
return answer;
}
//타겟 카드를 찾았을경우 같은 종류의 카드를 찾는 함수
Cursor findPair(int card, int x, int y, int count,int[][] board) {
Queue<Cursor> queue = new LinkedList<>();
boolean[][] visit = new boolean[4][4];
//타겟 카드부터 시작하기 때문에 같은 종류 카드로 인식 방지
board[y][x] = 0;
queue.add(new Cursor(x, y, count));
while (!queue.isEmpty()) {
Cursor current = queue.poll();
//같은 종류 카드를 찾으면 찾은 카드를 board에서 지워주고 현재 Cursor 반환
if (board[current.y][current.x] == card) {
board[y][x] = 0;
board[current.y][current.x] = 0;
return current;
}
if (visit[current.y][current.x])
continue;
visit[current.y][current.x] = true;
//방향키로만 이동
for (int i = 0; i < 4; i++) {
Cursor moveCursor = move(current.x, current.y, i);
if (moveCursor == null)
continue;
moveCursor.count += current.count;
queue.add(moveCursor);
}
//ctrl+방향키로만 이동
for (int i = 0; i < 4; i++) {
Cursor moveCursor = ctrlMove(current.x, current.y, i, board);
moveCursor.count += current.count;
queue.add(moveCursor);
}
}
//같은 종류의 카드를 못찾는 경우는 없다.(필요없는 값)
return new Cursor(x,y,count);
}
//찾고자하는 카드까지의 좌표와 거리(BFS)
Cursor findCard(int card, int x, int y, int count,int[][] board) {
Queue<Cursor> queue = new LinkedList<>();
boolean[][] visit = new boolean[4][4];
//시작하는 좌표와 현재 이동 거리를 넣어놓고 시작
queue.add(new Cursor(x, y, count));
while (!queue.isEmpty()) {
Cursor current = queue.poll();
//타겟 카드를 찾았을때의 Cursor 반환
if (board[current.y][current.x] == card)
return current;
if (visit[current.y][current.x])
continue;
visit[current.y][current.x] = true;
//방향키로만 이동
for (int i = 0; i < 4; i++) {
//이동했을때 범위를 벗어나면 null 반환
Cursor moveCursor = move(current.x, current.y, i);
if (moveCursor == null)
continue;
//moveCursor.count는 항상 1이다.
moveCursor.count += current.count;
queue.add(moveCursor);
}
//ctrl+방향키 이동
for (int i = 0; i < 4; i++) {
//이동하려는 방향에 카드가 있는지 어디로 이동해야하는지 판단후 Cursor반환
Cursor moveCursor = ctrlMove(current.x, current.y, i, board);
//moveCursor.count는 항상 1이다.
moveCursor.count += current.count;
queue.add(moveCursor);
}
}
//타겟 카드를 못찾는 경우는 없다.(필요없는 값)
return new Cursor(x, y, count);
}
//ctrl+방향키 이동
Cursor ctrlMove(int x, int y, int direction, int[][] board) {
int ny = y + dy[direction];
int nx = x + dx[direction];
//범위 끝에 도달할때 까지
while (ny >= 0 && nx >= 0 && ny < 4 && nx < 4) {
//중간에 카드가 있다면 카드까지만 이동
if (board[ny][nx] != 0)
return new Cursor(nx, ny, 1);
ny += dy[direction];
nx += dx[direction];
}
//끝까지 이동했을때 nx와 ny는 계산식으로 인해 범위를 오버했기 때문에 한칸 뒤로 물러준다.
return new Cursor(nx-dx[direction], ny-dy[direction], 1);
}
//방향키 이동
Cursor move(int x, int y, int direction) {
int ny = y + dy[direction];
int nx = x + dx[direction];
if (ny >= 0 && nx >= 0 && ny < 4 && nx < 4) {
return new Cursor(nx, ny, 1);
}
return null;
}
//카드의 방문순서 만드는 함수
void setOrders(int[] cardArr, int idx, String order, List<String> orders) {
if (idx == cardArr.length) {
orders.add(order);
return;
}
for (int i = 0; i < cardArr.length; i++) {
if (!order.contains("" + cardArr[i])) {
setOrders(cardArr, idx + 1, order + cardArr[i], orders);
}
}
}
HashSet<Integer> getCardSet(int[][] board) {
HashSet<Integer> cardSet = new HashSet<>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] != 0) {
cardSet.add(board[i][j]);
}
}
}
return cardSet;
}
int[][] copyBoard(int[][] board) {
int[][] copy = new int[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
copy[i][j] = board[i][j];
}
}
return copy;
}
class Cursor {
int x;
int y;
int count;
public Cursor(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
}Result
Reference
내 꿈은 좋은 개발자