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
Set<Integer> hs
에 저장List<List<card>> points
에 저장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));
}
}
}
카드 짝 맞추는 순서의
모든 경우의 수를 찾음짝 맞추는 순서 (1 --> 2 --> 3) int[]
로 표현
모든 경우의 수를 List<int[]> result
에 모두 저장
구해진 카드 짝 맞추는 모든 순서로 게임을 진행해서 가장 작은 비용을 구해야함
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);
Queue<List<Card>>
에 담아서 카드 짝 맞추기 시작Queue
는 카드 짝 맞추는 순서List<Card>
는 카드의 위치를 담고 있음 (항상 2개의 크기를 가짐)[1, 3, 2]
들어있다면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);
}
[1, 3, 2]
순서대로 진행되면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;
}
Control 키를 누르면 여러칸을 움직일 수 있는 것 때문에
문제의 난이도(Level 3)보다 높은 느낌을 받았다...
current
)가 end
의 위치이면 cost 에 비용 저장후 bfs 종료 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 이상의 문제들은 어렵다...