문제 유형
문제 접근
- 답
- 카드 짝을 전부 맞추기 위해 필요한 최소 명령 횟수
- 주어지는 정보
- 맵 크기 최대 4*4(int[][] board]
- 카드 개수 최대 7
- 후보
- 완전탐색
- 가능
- 맵 크기, 카드 개수가 충분히 작으므로 완전 탐색을 시도해 볼만함
- 과정
- 순열을 만든다(카드 짝을 맞추는 경우의 수 전부)
- 각 순열에 맞는 최소 명령 횟수를 구한다
import java.util.*;
class Card{
public int num,y,x;
public Card(int num,int y,int x){
this.num = num;
this.y = y;
this.x = x;
}
}
class XY{
public int y,x;
public int cnt;
public XY(int y, int x){
this.y = y;
this.x = x;
}
public XY(int y, int x, int cnt){
this.y = y;
this.x = x;
this.cnt = cnt;
}
}
class Solution {
ArrayList<XY>[] cardList = new ArrayList[7];
int cardCnt;
int N,M;
XY start;
public void copyBoard(int[][] copy, int[][] board){
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
copy[i][j] = board[i][j];
}
}
}
int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};
public int bfs(Deque<Card> orderDeque, int[][] board){
int value = 0;
int[][] copyBoard = new int[N][M];
copyBoard(copyBoard, board);
XY curStart = new XY(start.y, start.x,0);
for(int i = 0; i<cardCnt*2; i++){
Card targetCard = orderDeque.removeFirst();
orderDeque.addLast(targetCard);
int curValue = 0;
Queue<XY> queue = new LinkedList<>();
queue.add(curStart);
boolean[][] visited = new boolean[N][M];
visited[curStart.y][curStart.x] = true;
while(!queue.isEmpty()){
XY cur = queue.peek();
queue.poll();
if(cur.y == targetCard.y && cur.x == targetCard.x){
curValue = cur.cnt;
copyBoard[cur.y][cur.x] = 0;
break;
}
for(int j = 0; j<4; j++){
int moveY = cur.y + move[j][0];
int moveX = cur.x + move[j][1];
if(moveY < 0 || moveY >= N || moveX < 0 || moveX >= M){
continue;
}
if(visited[moveY][moveX] == true){
continue;
}
visited[moveY][moveX] = true;
queue.add(new XY(moveY,moveX,cur.cnt+1));
}
for(int j = 0; j<4; j++){
int moveY = cur.y;
int moveX = cur.x;
while(true){
moveY += move[j][0];
moveX += move[j][1];
if(moveY < 0 || moveY >= N || moveX < 0 || moveX >= M){
moveY -= move[j][0];
moveX -= move[j][1];
if(visited[moveY][moveX] == true){
break;
}
visited[moveY][moveX] = true;
queue.add(new XY(moveY,moveX,cur.cnt+1));
break;
}
if(copyBoard[moveY][moveX] != 0){
if(visited[moveY][moveX] == true){
break;
}
visited[moveY][moveX] = true;
queue.add(new XY(moveY,moveX,cur.cnt+1));
break;
}
}
}
}
curStart.y = targetCard.y;
curStart.x = targetCard.x;
value += curValue + 1;
}
return value;
}
int answer = Integer.MAX_VALUE;
int[][] choiceCard = {{0,1},{1,0}};
Deque<Card> orderDeque = new LinkedList<>();
boolean[] visited = new boolean[7];
public void dfs(int cnt, int[][] board){
if(cnt == cardCnt){
answer = Math.min(answer, bfs(orderDeque,board));
return;
}
for(int i = 1; i<=cardCnt; i++){
if(cardList[i].size() == 0){
continue;
}
if(visited[i] == true){
continue;
}
visited[i] = true;
for(int j = 0; j<2; j++){
XY xy1 = cardList[i].get(choiceCard[j][0]);
Card card1 = new Card(i,xy1.y,xy1.x);
XY xy2 = cardList[i].get(choiceCard[j][1]);
Card card2 = new Card(i,xy2.y, xy2.x);
orderDeque.addLast(card1);
orderDeque.addLast(card2);
dfs(cnt+1,board);
orderDeque.removeLast();
orderDeque.removeLast();
}
visited[i] = false;
}
}
public void setCardList(int[][] board){
for(int i = 0; i<=6; i++){
cardList[i] = new ArrayList<>();
}
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
if(board[i][j] != 0){
int num = board[i][j];
cardList[num].add(new XY(i,j));
}
}
}
}
public void setCardCnt(){
for(int i = 0; i<=6; i++){
if(cardList[i].size() != 0){
cardCnt++;
}
}
}
public int solution(int[][] board, int r, int c) {
N = board.length;
M = board[0].length;
setCardList(board);
setCardCnt();
start = new XY(r,c,0);
dfs(0,board);
return answer;
}
}
실패 코드
- 이유
- 규칙을 잘못 이해
- 하나의 객체에 전달하는 인자가 너무 많아서 가독성 떨어짐
- bfs()하나의 함수로만 구현했는데, 해당 함수가 가지는 역할이 너무 많음
import java.util.*;
class Member{
public int y,x;
public int targetY, targetX;
public int card = 0;
public int cnt = 0;
public boolean[] visited;
public Member(int y, int x, int targetY, int targetX, int card, int cnt, boolean[] visited){
this.y = y;
this.x = x;ㅠ
this.targetY = targetY;
this.targetX = targetX;
this.card = card;
this.cnt = cnt;
this.visited = visited;
}
}
class Solution {
public int[][] move = {{-1,0},{1,0},{0,1},{0,-1}};
public int N,M;
public int bfs(int[][] board, int r, int c){
int totalCard = totalCardPair(board);
boolean[] visited = new boolean[7];
int card = 0;
Queue<Member> q = new LinkedList<>();
q.add(new Member(r,c,-1,-1,0,0,setVisited(visited)));
while(!q.isEmpty()){
Member member = q.peek();
q.poll();
if(card > member.card){
continue;
}
card = Math.max(card, member.card);
if(card == totalCard){
return member.cnt;
}
int target = board[member.y][member.x];
if(target != 0 && visited[target] == false && (member.y != member.targetY || member.x != member.targetX)){
if(member.targetY == -1 && member.targetX == -1){
q.add(new Member(member.y,member.x,member.y,member.x,member.card,member.cnt+1,setVisited(member.visited)));
}
else if(member.targetY != -1 && member.targetX != -1){
int curTarget = board[member.targetY][member.targetX];
if(target == curTarget){
member.visited[target] = true;
member.targetY = -1;
member.targetX = -1;
member.cnt++;
member.card++;
q.add(member);
continue;
}
}
q.add(new Member(member.y,member.x,member.y,member.x,member.card,member.cnt+1,setVisited(member.visited)));
}
for(int i = 0; i<4; i++){
int moveY = member.y + move[i][0];
int moveX = member.x + move[i][1];
if(moveY < 0 || moveY >= N || moveX < 0 || moveX >= M){
continue;
}
q.add(new Member(moveY,moveX,member.targetY,member.targetX,member.card,member.cnt+1,setVisited(member.visited)));
}
q.add(new Member(member.y,0,member.targetY,member.targetX,member.card,member.cnt+1,setVisited(member.visited)));
q.add(new Member(member.y,M-1,member.targetY,member.targetX,member.card,member.cnt+1,setVisited(member.visited)));
q.add(new Member(0,member.x,member.targetY,member.targetX,member.card,member.cnt+1,setVisited(member.visited)));
q.add(new Member(N-1,member.x,member.targetY,member.targetX,member.card,member.cnt+1,setVisited(member.visited)));
}
return 0;
}
public boolean[] setVisited(boolean[] visited){
boolean[] temp = new boolean[7];
for(int i = 1; i<=6; i++){
temp[i] = visited[i];
}
return temp;
}
public int totalCardPair(int[][] board){
int card = 0;
for(int i = 0; i<board.length; i++){
for(int j = 0; j<board[i].length; j++){
if(board[i][j] == 0){
continue;
}
card++;
}
}
return card/2;
}
public int solution(int[][] board, int r, int c) {
int answer = 0;
N = board.length;
M = board[0].length;
answer = bfs(board,r,c);
return answer;
}
}