[13700] 완전범죄

13700번 완전범죄

이 문제는 불과 몇일 전에 틀렸던 문제다..

대충 2차원 공간에서 오른쪽 왼쪽으로만 움직일 수 있고, 앞으로 F만큼, 뒤로 B만큼 움직일 수 있는 조건에서 목적지까지 탈출하는 게임이다. 이때 문제는 버그(즉, 탈출이 불가능한 경우)가 있다면 BUG FOUND 없으면 누르는 버튼 횟수를 출력하는 문제다.

처음 풀었을 때

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

public class Main {

	public static int[] police = new int[10000000];
	public static int[] node = new int[1000000];
	public static boolean[] visit = new boolean[1000000];
	public static int N, S, D, F, B, K;
	
	public static int run(int s, int cnt) {
		int status = s;
		if(status == D) {
			//System.out.println(s +" "+ cnt);
			return cnt;
		}
		//전진 
		if(status+F<=N && status+F>=1&& node[status+F] != 1) {
			if(!visit[status+F]) {
				//System.out.println("F "+status+" "+(status+F)+" "+cnt);
				visit[status+F] = true;
				return run(status+F, cnt+1);
			}
			
		}
		//후진 
		else if(status-B<=N && status-B>=1&&node[status-B] != 1) {
			if(!visit[status-B]) {
				//System.out.println("B "+status+" "+(status-B)+" "+cnt);
				visit[status-B] = true;
				return run(status-B, cnt+1);
			}
			
		}
		return -1;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//N : 건물 개수 , S : 시작지점 , D : 목적지 , F : 전방 거리 , B : 후방거리 , K : 경찰서 수. 
		N = Integer.parseInt(st.nextToken()); S = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken()); F = Integer.parseInt(st.nextToken()); 
		B = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken());

		police = new int[K];
		node = new int[N+1];
		visit = new boolean[N+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<K ; i++) {
			police[i] = Integer.parseInt(st.nextToken());
			node[police[i]] = 1;
		}
		
		int cc = run(S, 0);
		if (cc == -1) {
			System.out.println("BUG FOUND");
		}
		else {
			System.out.println(cc);
		}
		
		
	}

}

DP로 풀 수 있을거라고 생각했는데, 생각해보니 visit 처리에 문제가 많았다. 시간날 때 다시 풀어야지 했는데….

14일 오후.. 아케인 주행한 뒤, 아브렐슈드(찬미버전) 듣다가 갑자기 생각나서 풀게되었다. 역시 사람은 좀 쉬면서 살아야…

역시 우리 섭주님!! 아브렐 눈나…! ㅠㅠㅠㅠ

아무튼, 그리하여 BFS로 다시 푼 결과 “맞았습니다”가 나왔다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken()); // 시작
		int D = Integer.parseInt(st.nextToken()); // 도착
		int F = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		//건물의 개수 N, 털린 금은방 S, 대도 X의 집 D, 앞으로 한 번에 달릴 수 있는 건물 수 F,
		//뒤로 한 번에 달릴 수 있는 건물 수 B, 마포구 경찰서의 개수 K, 각 경찰서의 건물 번호 l1, l2, …, lK가 주어질 때 
		int[] visit = new int[N+1];
		if(K>0) {
			int[] pstation = new int[K];
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<K; i++) {
				pstation[i] = Integer.parseInt(st.nextToken());
				visit[pstation[i]]=1;
			}
		}
		
		int[] count=new int[N+1];
		for(int i=0; i<N+1; i++) {
			count[i]=Integer.MAX_VALUE;
		}
		Queue<Integer> que = new LinkedList<Integer>();
		que.add(D);
		visit[D]=1;
		count[D]=0;
		while(!que.isEmpty()) {
			int q=que.poll();
			if(q+B<=N&&visit[q+B]==0) {
				que.add(q+B);
				count[q+B]=Math.min(count[q+B], count[q]+1);
				visit[q+B] = 1;
			}
			if(q-F>0 && visit[q-F]==0) {
				que.add(q-F);
				count[q-F]=Math.min(count[q-F], count[q]+1);
				visit[q-F] = 1;
			}
		}
		
		if(visit[S]==1) {System.out.println(count[S]);}
		else {
			System.out.println("BUG FOUND");
		}
		
	}

}

위 코드는 첫 시작을 목적지(탈출 목적지 D)로 시작했다. 굳이 S(금은방)부터 하지 않은 이유는 딱히 없다. 둘 중 뭐로 하든 if문에서 +,- 만 바뀌는 것이기 때문에 이는 취향껏..;;

원리는 간단!

1. 오른쪽-왼쪽으로 각각 갔을 때 이미 방문하지 않은 경우 가본다.
2. 진행이 가능하다면, 이전 스탭에서 카운트를 +1한다.

이를 반복하다가, 만약 S 출발지점에 갈 수 있는 경우 해당 카운트를 출력하고, 아니라면 BUG FOUND를 출력하면 된다.!