Life Engineering
[프로그래머스] 카드 짝 맞추기 (Java) 본문
https://programmers.co.kr/learn/courses/30/lessons/72415
import java.util.*;
class Solution {
static int[][] pairs = new int[7][4];
static int answer = Integer.MAX_VALUE;
static int limit = 0;
static ArrayList<Integer> numbers = new ArrayList<>();
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
public int solution(int[][] board, int r, int c) {
for (int i = 0; i < 7; i++) {
Arrays.fill(pairs[i], -1);
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] != 0) {
int num = board[i][j];
if (pairs[num][0] == -1) {
pairs[num][0] = i;
pairs[num][1] = j;
limit++;
numbers.add(num);
} else {
pairs[num][2] = i;
pairs[num][3] = j;
}
}
}
}
perm(r, c, board, 0, 0, new boolean[7]);
return answer;
}
public void perm(int r, int c, int[][] board, int cnt, int sum, boolean[] visited) {
if (sum > answer)
return;
if (cnt == limit) {
answer = Math.min(answer, sum);
return;
}
//System.out.println(r + " " + c);
for (int i = 0; i < numbers.size(); i++) {
int picked = numbers.get(i);
if (visited[picked])
continue; // 뒤집을 카드를 정함
visited[picked] = true;
int dist1 = bfs(r, c, pairs[picked][0], pairs[picked][1], picked, board)
+ bfs(pairs[picked][0], pairs[picked][1], pairs[picked][2], pairs[picked][3], picked, board);
board[pairs[picked][0]][pairs[picked][1]]=0;
board[pairs[picked][2]][pairs[picked][3]]=0;
perm(pairs[picked][2], pairs[picked][3], board, cnt + 1, sum + dist1 + 2, visited);
board[pairs[picked][0]][pairs[picked][1]]=picked;
board[pairs[picked][2]][pairs[picked][3]]=picked;
int dist2 = bfs(r, c, pairs[picked][2], pairs[picked][3], picked, board)
+ bfs(pairs[picked][2], pairs[picked][3], pairs[picked][0], pairs[picked][1], picked, board);
board[pairs[picked][0]][pairs[picked][1]]=0;
board[pairs[picked][2]][pairs[picked][3]]=0;
perm(pairs[picked][0], pairs[picked][1], board, cnt + 1, sum + dist2 + 2, visited);
board[pairs[picked][0]][pairs[picked][1]]=picked;
board[pairs[picked][2]][pairs[picked][3]]=picked;
visited[picked] = false;
}
}
private int bfs(int start_r, int start_c, int dest_r, int dest_c, int num, int[][] board) { // start~dest 까지 비용 계산
int r, c, cnt, nr, nc;
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[4][4];
q.add(new int[] { start_r, start_c, 0 });
visited[start_r][start_c] = true;
while (!q.isEmpty()) {
int[] curr = q.poll();
r = curr[0];
c = curr[1];
cnt = curr[2];
if (r == dest_r && c == dest_c) {
return cnt;
}
for (int i = 0; i < 4; i++) {
nr = r + dr[i];
nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= 4 || nc >= 4)
continue;
if (!visited[nr][nc]) {
q.add(new int[] { nr, nc, cnt + 1 });
visited[nr][nc] = true;
}
}
for (int i = 0; i < 4; i++) {
nr = r;
nc = c;
while (true) {
nr += dr[i];
nc += dc[i];
if (nr < 0 || nc < 0 || nr >= 4 || nc >= 4) {
nr -= dr[i];
nc -= dc[i];
break;
}
if (board[nr][nc] != 0) {
break;
}
}
if (!visited[nr][nc]) {
q.add(new int[] { nr, nc, cnt + 1 });
visited[nr][nc] = true;
}
}
}
return -1;
}
}
https://yjyoon-dev.github.io/kakao/2021/01/29/kakao-paircard/
완전탐색+시뮬레이션 문제
뒤집을 카드의 순서를 정하고=>뒤집을 카드를 정했으면 1번째 카드 먼저 뒤집을 것인지, 2번째 카드 먼저 뒤집을 것인지 나눈다. (perm 함수)
이후 BFS 함수에서 start 카드에서 dest 카드까지 갈 수 있는 최소 거리를 구해준다.
비용 계산은 현재 놓인 카드 위치~(1 또는 2 번째 카드 위치)~(2 또는 1번째 카드 위치)를 더한 값에다, +2를 더해준다. (엔터 2번)
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 셔틀버스 (Java) (0) | 2022.05.07 |
---|---|
[프로그래머스] 주차 요금 계산 (Java) (0) | 2022.05.06 |
[BOJ 13460] 구슬 탈출2 (Java) (0) | 2022.04.29 |
[BOJ 19237] 어른 상어 (Java) (0) | 2022.04.27 |
[BOJ 23289] 온풍기 안녕! (Java) (0) | 2022.04.26 |