[프로그래머스(Programmers)][자바(java)] (Lv3) 카드 짝 맞추기

 

programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

 

문제 요약

• 현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성
• 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
  유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

• 카드는 커서를 이용해서 선택할 수 있습니다.
• 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
  • 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
  • [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
    • 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
  • 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
• 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.

• 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산

• board는 4 x 4 크기의 2차원 배열입니다.
• board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
  • 0은 카드가 제거된 빈 칸을 나타냅니다.
  • 1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
  • 뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
• r은 커서의 최초 세로(행) 위치를 의미합니다.
• c는 커서의 최초 가로(열) 위치를 의미합니다.
• r과 c는 0 이상 3 이하인 정수입니다.
• 게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.

 

문제 풀이

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	
	class Card {
		int x, y, k, m;  // ( x, y ), k : chracter's kind in the card, m : num of moves
		Card( int x, int y, int k, int m ) {
			this.x = x;
			this.y = y;
			this.k = k;
			this.m = m;
		}
	}
	
	int cnt_m, bd[][], ix, iy, dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
	HashMap<Integer, Card[]> hm;  // key => kind of character, val => coord of two Card
	
	public int getMinCnt( int b[][], Card c1, Card c2 ) {  /* c1 ~ c2 최소 이동 횟수 */
		int sx = c1.x, sy = c1.y, ex = c2.x, ey = c2.y;  // start x/y, end x/y
		if( sx == ex && sy == ey )
			return 0;
		int x, y, m, nx, ny, nk, nm, nnx, nny, i;  // next x/y/k/m
		boolean v[][];
		Queue<Card> q = new LinkedList<>();
		q.add( new Card( sx, sy, b[sx][sy], 0 ) );
		Card c;
		while( !q.isEmpty() ) {
			c = q.remove();
			x = c.x; y = c.y; m = c.m;
			v = new boolean[4][4];
			v[x][y] = true;
			loop:
			for( i = 0; i < 4; i++ ) {
				/* right, down, left, up */
				nx = x+dx[i]; ny = y+dy[i]; 
				if( nx < 0 || nx >= 4 || ny < 0 || ny >= 4  )
					continue;  /* 더 이상 이동할 수 없는 경우 */
				if( v[nx][ny] )
					continue;  /* 이미 방문한 칸 일 경우 */
				nm = m+1;
				if( nx == ex && ny == ey )
					return nm;
				v[nx][ny] = true;
				nk = b[nx][ny];
				q.add( new Card( nx, ny, nk, nm ) );
				if( nk > 0 )
					continue;  /* ctrl+ 이동과 같을 경우 */
				/* ctrl  +  right, down, left, up */
				nx += dx[i]; ny += dy[i];
				if( nx < 0 || nx >= 4 || ny < 0 || ny >= 4  )
					continue;  /* 더 이상 이동할 수 없는 경우 */
				while( true ) {
					if( v[nx][ny] )
						continue loop;
					v[nx][ny] = true;
					if( nx == ex && ny == ey )
						return nm;
					nk = b[nx][ny];
					if( nk > 0 ) {
						q.add( new Card( nx, ny, nk, nm ) );
						continue loop;  /* 가장 가까운 카드 */
					}
					nnx = nx+dx[i]; nny = ny+dy[i];
					if( nnx < 0 || nnx >= 4 || nny < 0 || nny >= 4  )
						break;  /* 더 이상 이동할 수 없는 경우 */
					nx += dx[i]; ny += dy[i];
				}
				q.add( new Card( nx, ny, nk, nm ) );  /* 가장 마지막 칸 */
			}
		}
		return 0;
	}
	
	public void perm( int k, int n, int d[], int a[], boolean v[] ) {  
	// k : cnt var, n : len of data arr, d[] : data arr, a[] : arr, v[] : visited 
		int i, j;
		if( k == n ) {
			int b[][] = new int[4][4];  // board arr
			for( i = 0; i < 4; i++ )
				for( j = 0; j < 4; j++ )
					b[i][j] = bd[i][j];
			int cx = ix, cy = iy, cnt = 0, ct, c, idx = 0;  // cursor x/y
			Card cd[], cur;  // card arr, cursor card
			for( i = 0; i < n; i++ ) {
				ct = Integer.MAX_VALUE;
				cd = hm.get( d[a[i]] );  // card arr to find
				cur = new Card( cx, cy, b[cx][cy], 0 );
				for( j = 0; j < 2; j++ ) {
					c = 0;
					c += getMinCnt( b, cur, cd[j] ) + 1;
					c += getMinCnt( b, cd[j], cd[1-j] ) + 1;
					if( ct > c ) {
						ct = c;
						idx = 1-j;  // next cursor cd[] idx
					}
				}
				cnt += ct;
				b[cd[0].x][cd[0].y] = b[cd[1].x][cd[1].y] = 0;
				cx = cd[idx].x;
				cy = cd[idx].y;
			}
			if( cnt_m > cnt )
				cnt_m = cnt;
		}
		for( i = 0; i < n; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				a[i] = k;
				perm( k+1, n, d, a, v );
				v[i] = false;
			}
		}
	}
	
	public int solution(int[][] board, int r, int c) {
		cnt_m = Integer.MAX_VALUE;  // count minimum
		bd = board;
		ix = r;  // initial x/y
		iy = c;
		hm = new HashMap<>();
		int i, j, k;
		for( i = 0; i < 4; i++ ) {
			for( j = 0; j < 4; j++ ) {
				k = board[i][j];  // kind of the chracter in the card
				if( k == 0 )
					continue;
				if( hm.containsKey( k ) ) 
					hm.get( k )[1] = new Card( i, j, k, 0 );
				else {
					hm.put( k, new Card[2] );
					hm.get( k )[0] = new Card( i, j, k, 0 );
				}
			}
		}
		int s = hm.size(), ks[] = new int[s], idx=  0; 
		for( int kk : hm.keySet() )
			ks[idx++] = kk;
		perm( 0, s, ks, new int[s], new boolean[s] );
		return cnt_m;
	}
}

 

*  BFS, 완전 탐색( 순열 )

-  Card class 생성 ( x 좌표, y 좌표, 카드의 캐릭터 종류( board[x][y] ), 이동 횟수 )

-  입력받은 int board[][] 배열을 탐색하며 카드의 캐릭터 종류와 각각의 위치를 저장하기 위해
   HashMap<Integer,Card[]> hm을 생성

-  캐릭터의 종류를 담을 배열 int ks[] 생성

-  뒤집을 카드를 뽑는 모든 경우의 수( 순열 )를 구하기 위해 함수 void perm() 생성

-  각각의 경우의 수 마다 ‘현재 커서 -> 뒤집을 카드 -> 그 카드의 짝’ 의 최소 이동 횟수를 구하기 위해  
   시작 좌표와 끝 좌표를 매개 변수로 하여 두 좌표 간 최소 이동 횟수를 리턴하는 함수  int getMinCnt() 생성
   -  상, 하, 좌, 우, ctrl 상, ctrl 하, ctrl 좌, ctrl 우 의 8가지 이동 방법에 대해 BFS로 이동 가능한 좌표를 구함
  ┌  현재 커서  ->  뒤집을 카드 ( 첫 번째 / 두 번째 )
  └  뒤집을 카드  ->  그 카드의 짝 ( 두 번째 / 첫 번째 )