[BOJ] 백준 1405 미친 로봇 - Python/Java

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

1405번: 미친 로봇

해설

깊이 우선 탐색을 이용해서 방문했던 곳을 다시 방문하지 않는 조건으로 모든 지점을 완전 탐색하는 문제입니다.

 

깊이 우선 탐색을 이용해서 네 방향으로 N번 이동하게 될 때, 가능한 총 경우의 수는 4^N입니다. 따라서 문제에서 주어진 N <= 14라는 조건을 감안하면 모든 경우의 수를 탐색하는 것은 시간복잡도 상 불가능합니다.

 

다만, 이 문제에서는 '방문했던 곳을 재방문하면 안 된다'는 조건이 있으므로 매 시점 다음 이동을 정할 때, 이미 방문한 곳을 제외함으로써 시간복잡도를 줄일 수 있죠.

 

한편, 문제에서 N <= 14라고 했으므로, 이차원 배열에서 점을 움직인다고 생각하려고 합니다. 그러면 대충 30 * 30 크기의 이차원 배열에서 가운데 지점인 (15, 15)에서 시작하면 상하좌우로 직진을 해도 배열의 크기를 벗어나지 않게 되죠. 이런 상황에서는 배열의 크기를 벗어나는지에 대한 IndexOutOfBounds 예외를 체크해주지 않아도 되기 때문에 편리합니다.

 

결국 이 문제의 풀이는 간단해집니다.

 

1. N을 입력받고, 적당한 크기의 격자를 생성한다.

2. 격자의 중앙에서 시작하여 최초 방문하는 곳만 깊이 우선 탐색으로 방문하여 N번을 이동한다.

3. 이동을 할 때마다 해당 확률을 현재 확률에 곱사건으로 처리해주고, 최종적으로 해당 지점까지 올 수 있게 한 확률 p를 정답에 더해준다.

 

풀이는 아래와 같습니다.

 

풀이 - 파이썬

def dfs(x, y, visited, count, p):
    global answer
    if count == n:
        answer += p
        return
            
    visited[x][y] = True
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if not visited[nx][ny]:
            dfs(nx, ny, visited, count+1, p * prob[i])
            visited[nx][ny] = False
            
line = list(map(int, input().split()))
n, prob = line[0], list(map(lambda x : x / 100, line[1:]))
answer = 0
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0] # 동서남북

# 100*100 크기의 격자를 만들고 초기 위치를 (50, 50)으로 설정
visited = [[False] * (100) for _ in range(100)]
dfs(50, 50, visited, 0, 1)
print(answer)

 

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_1405 {
    static int n;
    static double answer;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static double[] prob = new double[4];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 입력 받기
        n = Integer.parseInt(st.nextToken());
        for(int i = 0; i < 4; i++){
            prob[i] = (Double.parseDouble(st.nextToken()) / 100);
        }

        boolean[][] visited = new boolean[100][100];
        dfs(50, 50, visited, 0, 1);
        System.out.println(answer);
    }

    // 깊이 우선 탐색
    public static void dfs(int x, int y, boolean[][] visited, int count, double p){
        if(count == n){ // n번 이동해서 반복된 곳 방문안하면 해당 확률을 더해준다.
            answer += p;
            return;
        }

        visited[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(!visited[nx][ny]){ // 이미 방문한 곳 제외하고 재귀적으로 방문
                dfs(nx, ny, visited, count+1, p * prob[i]);
                visited[nx][ny] = false;
            }
        }
    }
}