알고리즘 풀이 - 백준 16197(두 동전, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

NxM 크기의 보드와 4개의 버튼으로 이루어진 게임에서 벽, 동전, 빈칸이 있을 때, 동전은 2개가 주어져 위치한다고 하는 경우 최소한의 움직임으로 동전을 1개만 외부로 떨어뜨리는 움직임의 횟수를 구하는 문제

 

 

2. 풀이

 

완전 탐색 기법을 통해 시뮬레이션으로 구현하는 방식으로 해결한 문제이다.

실제로 모든 방향으로 동전을 이동시킨 뒤, 1개만 떨어지는 모든 경우를 체크하여 그 경우가 최소가 되는지를 조사하였다.

10회 이상 움직였거나 현재의 최소값 이상으로 움직인 경우에는 추가 탐색을 종료한다. 해결한 방법은 다음과 같다.

① 각 동전의 초기 위치를 저장할 별도 Class를 생성하여 저장한다.
② 현재 이동한 횟수, 동전의 위치를 저장한 Object 변수를 전달하여 재귀 함수를 수행한다.
③ 재귀 함수 내에서 반복문을 통해 동전을 이동시키고 2개가 떨어졌다면 해당 경우는 무시 후 다시 반복문을 수행한다.
④ 1개만 떨어졌다면 현재 이동 횟수 + 1을 하고 최소값과 비교하여 갱신하고 이전 재귀 함수로 돌아간다.
⑤ 동전이 벽의 위치로 이동했다면 다시 원 위치 시킨다.
⑥ 모든 재귀 수행 시 10번 이상 이동했거나, 현재 최소값 이상 이동 시 추가 탐색을 하지 않고 돌아간다.

 

위 내용을 참고하여 아래 코드를 통해 정답을 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static int m;
    static char[][] board;
    static int y1, x1, y2, x2;  // 코인 2개의 위치 저장
    static int[] dy = {-1, 0, 1, 0};  // y방향 움직임
    static int[] dx = {0, -1, 0, 1};  // x방향 움직임
    static int ans = 11; // 11을 기본값으로 두고 변경 없으면 -1 출력
    public static void main(String[] args) throws IOException{
    
        // ********************** 주어진 값 저장 *********************
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new char[n][m];
        
        int c = 0; // 현재 코인의 개수
        for(int i=0; i < n; i++){
            String s = br.readLine();
            for(int j=0; j < m; j++){
                board[i][j] = s.charAt(j);
                if(board[i][j] == 'o'){
                    if(c == 0){
                        y1 = i;
                        x1 = j;
                    } else {
                        y2 = i;
                        x2 = j;
                    }
                    // 코인 개수 ++
                    c++;
                }
            }
        }
        // ******************** 주어진 값 저장 완료 *******************
        
        // ******************* 완전 탐색 수행 및 결과 출력 *****************
        bruteForce(new Coin(y1, x1, y2, x2), 0);
        if(ans == 11){
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
        br.close();
        // ******************* 완전 탐색 및 결과 출력 완료 ******************
    }
    
    // 완전 탐색을 수행하는 메소드
    private static void bruteForce(Coin coins, int move){
        // 현재 이동 횟수가 최소값보다 커졌거나 10회 이상 시 탐색 종료
        // move > ans 부분을 통해 반복 움직임으로 인한 경우를 방지함
        if(move > ans || move > 10) return;
        
        for(int i=0; i < 4; i++){
            int out = 0;
            int ny1 = coins.y1 + dy[i];
            int nx1 = coins.x1 + dx[i];
            int ny2 = coins.y2 + dy[i];
            int nx2 = coins.x2 + dx[i];
            
            
            // 보드 밖으로 나갔다면 out을 추가함
            if(ny1 < 0 || ny1 >= n || nx1 < 0 || nx1 >= m){
                out++;
            }
            if(ny2 < 0 || ny2 >= n || nx2 < 0 || nx2 >= m){
                out++;
            }
            
            // 2개가 나간 경우는 제외해야 함
            if(out == 2) continue;
            
            // 1개만 나간 경우 현재 움직인 횟수를 비교하고 반환
            if(out == 1) {
                ans = Math.min(ans, move+1);
                return;
            }
            
            // 벽으로 이동한 경우는 다시 원래 값으로 저장
            if(board[ny1][nx1] == '#'){
                ny1 = coins.y1;
                nx1 = coins.x1;
            }
            
            if(board[ny2][nx2] == '#'){
                ny2 = coins.y2;
                nx2 = coins.x2;
            }
            
            // 다음 위치에서 완전 탐색 추가 수행
            bruteForce(new Coin(ny1, nx1, ny2, nx2), move+1);
        }
    }
}

class Coin{
    int y1;
    int x1;
    int y2;
    int x2;
    public Coin(int y1, int x1, int y2, int x2){
        this.y1=y1;
        this.x1=x1;
        this.y2=y2;
        this.x2=x2;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.