[프로그래머스 LV3] 카드 짝 맞추기 (2021 KAKAO BLIND RECRUTMENT, 구현, 순열, BFS)

🧐 프로그래머스 LV3. 카드 짝 맞추기

문제 설명

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.
게임에서 카드를 선택하는 방법은 다음과 같습니다.

- 카드는 커서를 이용해서 선택할 수 있습니다.
  - 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 "굵고 빨간 테두리 상자"를 의미합니다.
- 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
  - 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
  - [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
    - 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
  - 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
- 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
  - [Enter] 키를 입력해서 카드를 뒤집었을 때
    - 앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
    - 앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.

"베로니"는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.

현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

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

입출력 예

board	r	c	result
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]]	1	0	14
[[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]]	0	1	16

https://school.programmers.co.kr/learn/courses/30/lessons/72415

프로그래머스

 

💡 문제 풀이

카카오 코테 기출답게 문제 이해부터 어려웠고, 정답 풀이 방식을 이해하는 데도 한참 걸렸다. 💦

구현, 순열, bfs 유형이 모두 섞인 문제였다. 순열과 bfs 개념은 알고 있다는 가정 하에 문제 풀이를 적어보도록 하겠다.

 

우선 요약을 해보자면,,,

게임판(board)에 있는 숫자 카드를 찾는 순서를 순열로 구해서 각 bfs 알고리즘을 돌린다.

카드를 하나씩 찾을 때마다 최소 거리를 더해주고, 큐를 비워주고 다음 카드를 찾아 다시 시작한다.

모든 카드를 찾았으면 전역 변수 answer(모든 경우의 값 중 최솟값)과 비교해서 최솟값으로 업데이트 해준다.

 

필요한 전역 변수들을 정의한다.

static boolean[] isNum = new visited[7]; // 숫자 카드: 게임판에 있으면 true, 아니면 false
static boolean[] visited = new visited[7]; // 순열에서 사용하는 방문 체크 배열

static int size = 0; // 존재하는 숫자 카드 개수 (중복없이)
static int answer = Integer.MAX_VALUE; // 문제 답: 최소 키 조작 횟수

static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
    
static class Point { // 게임판 내 위치
	int x, y, d;
        
	Point(int x, int y, int d) {
		this.x = x; // row
		this.y = y; // column
		this.d = d; // 이동 거리(키 조작 횟수)
	}
}

 

solution 메소드

public int solution(int[][] board, int r, int c) {
        
	// 게임판에 있는 카드 확인
	for(int i = 0; i < 4; i++) {
		for(int j = 0; j < 4; j++) {
        	// 카드가 없는 칸이거나, 이미 확인한 카드 종류이면 pass
			if(board[i][j] == 0 || isNum[board[i][j]]) continue;
               
			isNum[board[i][j]] = true; // 카드 존재 확인
			size++; // 카드 종료 개수 + 1
		}
	}
        
	// 순열: 카드 탐색 순서
	permutation(0, new int[size], board, r, c);

	// 모든 탐색의 경우의 수에서 최소 조작 개수 값 반환
	return answer;
}

 

permutation 메소드 : 순열, 카드 탐색 순서를 구한다.

// cnt: 뽑은 수 개수, arr: 카드 탐색 순서
private void permutation(int cnt, int[] arr, int[][] board, int r, int c) {
	if(size == cnt) { // 순열 끝났으면 arr 순서대로 bfs 돌리기
		bfs(board, r, c, arr);
		return;
	}
        
	for(int i = 1; i <= 6; i++) {
            if(visited[i] || !isNum[i]) continue; // 없는 카드이거나 방문했으면 pass

            visited[i] = true;
            arr[cnt] = i;
            permutation(cnt + 1, arr, board, r, c);
            visited[i] = false;
	}
}

 

bfs 메소드 : 순서대로 카드를 탐색하면서 최소 키 조작 횟수를 구한다.

private void bfs(int[][] board, int r, int c, int[] arr) {
	// 위치 정보 큐
	Queue<Point> queue = new LinkedList<>();
	queue.add(new Point(r, c, 0));
    
	// 위치 방문 여부 저장
	boolean[][] isVisited = new boolean[4][4];
	isVisited[r][c] = true;
    
	// 카드를 찾았는지(enter) 여부 저장
	boolean[][] enterVisited = new boolean[4][4];
    
	int answerCnt = 0; // 전체 키 조작 횟수
	int idx = 0; // 카드 탐색 순서 배열 인덱스
	boolean isSecond = false; // 두번째 카드 탐색 여부
        
	while(!queue.isEmpty()) {
		Point cur = queue.poll();
            
		// 찾고자하는(arr[idx]) 카드를 처음(!enterVisited) 찾았을 때
		if(board[cur.x][cur.y] == arr[idx] && !enterVisited[cur.x][cur.y]) {
			enterVisited[cur.x][cur.y] = true;
			answerCnt++; // enter 키
 			answerCnt += cur.d; // 최단 이동 거리 더하기

			// 큐 초기화 (다음 카드 탐색 시작 준비)
 			queue.clear();
			queue.add(new Point(cur.x, cur.y, 0)); 
			isVisited = new boolean[4][4];
			isVisited[cur.x][cur.y] = true;
                
			if(!isSecond) { // 같은 종류에서 첫번째로 찾은 카드일 때
				isSecond = true;
			} else { // 두번째로 찾은 카드일 때
				isSecond = false;
				idx++; // 다음 카드 유형
				if(idx >= arr.length) { // 모든 카드를 찾았을 때
					answer = Math.min(answer, answerCnt); // 최솟값 업데이트
					return;
				}
			}
                
			continue;
		}
            
		for(int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];

			// 한 칸 이동
			if(0 <= nx && nx < 4 && 0 <= ny && ny < 4 && !isVisited[nx][ny]) {
				isVisited[nx][ny] = true;
				queue.add(new Point(nx, ny, cur.d + 1));
			}

			// 한 칸 이동하기 전 위치로 다시 초기화
			nx -= dx[i];
			ny -= dy[i];

			// ctrl 이용해서 끝까지 이동
			while(0 <= nx + dx[i] && nx + dx[i] < 4 && 0 <= ny + dy[i] && ny + dy[i] < 4) {
				nx += dx[i];
				ny += dy[i];

				// 중간에 enter 하지 않은 카드가 있다면 멈춤
				if(board[nx][ny] != 0 && !enterVisited[nx][ny]) {
					break;
				}
			}

			// ctrl 이동
			if(0 <= nx && nx < 4 && 0 <= ny && ny < 4 && !isVisited[nx][ny]) {
				isVisited[nx][ny] = true;
				queue.add(new Point(nx, ny, cur.d + 1));
			}
		}
	}
}

 

풀이 방식을 전체 코드로 풀어내면 아래와 같다.

import java.util.*;

class Solution {
    
    static boolean[] isNum = new boolean[7];
    static boolean[] visited = new boolean[7];
    static int size = 0;
    static int answer = Integer.MAX_VALUE;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    static class Point {
        int x;
        int y;
        int d;
        
        Point(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
    
    public int solution(int[][] board, int r, int c) {
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                if(board[i][j] == 0 || isNum[board[i][j]]) {
                    continue;
                }
                
                isNum[board[i][j]] = true;
                size++;
            }
        }
        
        permutation(0, new int[size], board, r, c);
        
        return answer;
    }
    
    private void bfs(int[][] board, int r, int c, int[] arr) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(r, c, 0));
        
        boolean[][] isVisited = new boolean[4][4];
        isVisited[r][c] = true;
        
        boolean[][] enterVisited = new boolean[4][4];
        
        int answerCnt = 0;
        int idx = 0;
        boolean isSecond = false;
        
        while(!queue.isEmpty()) {
            Point cur = queue.poll();
            
            // 카드 일치
            if(board[cur.x][cur.y] == arr[idx] && !enterVisited[cur.x][cur.y]) {
                enterVisited[cur.x][cur.y] = true;
                answerCnt++; // enter
                answerCnt += cur.d; // 최단 이동 거리
                
                queue.clear();
                queue.add(new Point(cur.x, cur.y, 0));
                
                isVisited = new boolean[4][4];
                isVisited[cur.x][cur.y] = true;
                
                if(!isSecond) {
                    isSecond = true;
                } else {
                    isSecond = false;
                    idx++;
                    
                    if(idx >= arr.length) {
                        answer = Math.min(answer, answerCnt);
                        return;
                    }
                }
                
                continue;
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                // 한 칸 이동
                if(0 <= nx && nx < 4 && 0 <= ny && ny < 4 && !isVisited[nx][ny]) {
                    isVisited[nx][ny] = true;
                    queue.add(new Point(nx, ny, cur.d + 1));
                }
                
                // 한 칸 이동하기 전 위치로 다시 초기화
                nx -= dx[i];
                ny -= dy[i];
                
                // ctrl 이용해서 끝까지 이동
                while(0 <= nx + dx[i] && nx + dx[i] < 4 && 0 <= ny + dy[i] && ny + dy[i] < 4) {
                    nx += dx[i];
                    ny += dy[i];
                    
                    // 중간에 enter 하지 않은 카드가 있다면 멈춤
                    if(board[nx][ny] != 0 && !enterVisited[nx][ny]) {
                        break;
                    }
                }
                
                // ctrl 이동
                if(0 <= nx && nx < 4 && 0 <= ny && ny < 4 && !isVisited[nx][ny]) {
                    isVisited[nx][ny] = true;
                    queue.add(new Point(nx, ny, cur.d + 1));
                }
            }
        }
    }
    
    private void permutation(int cnt, int[] arr, int[][] board, int r, int c) {
        if(size == cnt) { // arr 순서대로 bfs 돌리기
            bfs(board, r, c, arr);
            return;
        }
        
        for(int i = 1; i <= 6; i++) {
            if(visited[i] || !isNum[i]) { // 없는 카드이거나 방문했으면 pass
                continue;
            }
            
            visited[i] = true;
            arr[cnt] = i;
            permutation(cnt + 1, arr, board, r, c);
            visited[i] = false;
        }
    }
}

 

✨ 포스팅을 마치며

너무너무 어렵고 이해하는데도 긴 시간이 걸렸지만, 새로운 풀이 방법을 한 번에 알게 되서 좋았다. 👍