[백준] 16197. 두 동전

https://www.acmicpc.net/problem/16197

풀이

상,하,좌,우 4방향에 대해서 완탐을 돌렸다. 맵 밖으로 나갈 때 동전개수를 감소시켜주고 하나만 떨어졌을 때를 ans 를 갱신시켜 줬다.

만약 다음에 움직일 칸이 '#' 이라면 현재 위치로 다시 값을 세팅해주고 다음 depth 로 넘어간다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static int height;
    private static int width;
    private static char[][] map;
    private static int[][] visit;
    private static int dy[] = {1, -1, 0, 0};
    private static int dx[] = {0,0,1,-1};
    private static int ans = 987654321;


    private static List<Integer[]> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());
        map = new char[height][width];

        for (int i = 0; i < height; i++) {
            String row = br.readLine();
            for (int j = 0; j < width; j++) {
                map[i][j] = row.charAt(j);
                if (row.charAt(j) == 'o') {
                    list.add(new Integer[]{i, j});
                    map[i][j] = '.';
                }
            }
        }


        solve(0,0,list.get(0)[0] , list.get(0)[1] , list.get(1)[0] , list.get(1)[1],2);
        if(ans == 987654321){
            System.out.println(-1);
        }else
            System.out.println(ans+1);

    }

    private static void solve(int depth , int cnt , int fy, int fx , int sy , int sx , int coins){
        if(ans < cnt) return;
        if (depth >= 10) {
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nfy = fy + dy[i];
            int nfx = fx + dx[i];

            int nsy = sy + dy[i];
            int nsx = sx + dx[i];

            int countCoin = 2;

            if(nfy < 0 || nfx < 0 || nfy >= height || nfx >= width) countCoin--;
            if(nsy < 0 || nsx < 0 || nsy >= height || nsx >= width) countCoin--;

            
            if(countCoin == 0) continue;
            else if(countCoin == 1){
                if(ans > cnt) ans = cnt;
            }else {

                if(map[nfy][nfx] == '#') {
                    nfy = fy;
                    nfx = fx;
                }
                if(map[nsy][nsx] == '#') {
                    nsy = sy;
                    nsx = sx;
                }
                solve(depth + 1, cnt + 1, nfy, nfx, nsy, nsx,2);
            }
        }





    }

}