[BOJ/백준] 20041 Escaping - 자바,파이썬

문제

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

20041번: Escaping

icpc 2020 예선 F번 문제로

도둑과 경찰에 대한 정보가 주어졌을 때, 도둑이 경찰에게서 탈출할 수 있는지 판단하는 문제

 

문제풀이

도둑이 경찰에게서 가장 멀리 달아날 수 있는 방법은 4 방향 중 한 방향으로 직진 하는 방법이다.

각 경찰에 대해서 위, 아래, 왼쪽, 오른쪽 방향을 탐색한다.

한 번이라도 탈출할 수 있다면 초기 조건에서 탈출 가능한 것

  ex) 위로 움직일 때.

    - 경찰이 도둑보다 밑에 있으면 탈출 가능

    - 경찰이 도둑보다 위에 있고, 그 거리가 좌우로 떨어진 거리보다 길면 탈출 불가능

 

 

 

코드

1.java

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	static int n;
	static int police[][],x,y;
	
	public static boolean find(int move) { //도둑이 움직이는 위치를 바탕으로
		for(int i=0;i<n;i++) {
			if(move==0) { //위로
				if(police[i][1]<=y) //탈출가능
					continue;
				int temp=police[i][0]>x?police[i][0]-x:x-police[i][0];
				if((police[i][1]-y)>=temp) //잡힘
					return false;
			}
			else if(move==1) {//아래
				if(police[i][1]>=y)
					continue;
				int temp=police[i][0]>x?police[i][0]-x:x-police[i][0];
				if((y-police[i][1])>=temp)
					return false;
			}
			else if(move==2) { //왼쪽
				if(police[i][0]>=x)
					continue;
				int temp=police[i][1]>y?police[i][1]-y:y-police[i][1];
				if((x-police[i][0])>=temp)
					return false;
			}
			else if(move==3){//오른쪽
				if(police[i][0]<=x)
					continue;
				int temp=police[i][1]>y?police[i][1]-y:y-police[i][1];
				if((police[i][0]-x)>=temp)
					return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(bf.readLine());
		police=new int [n][2];
		for(int i=0;i<n;i++) {
			StringTokenizer st1=new StringTokenizer(bf.readLine());
			police[i][0]=Integer.parseInt(st1.nextToken());
			police[i][1]=Integer.parseInt(st1.nextToken());
		}
		
		StringTokenizer st=new StringTokenizer(bf.readLine());
		x=Integer.parseInt(st.nextToken());
		y=Integer.parseInt(st.nextToken());
		boolean result = false;
		for(int i=0;i<4;i++) {
			result=find(i);
			if(result==true)
				break;
		}
		
		if (result==true)
			System.out.println("YES");
		else
			System.out.println("NO");
		
	}

}

 

2. 파이썬

n=int(input())
def find(move):
    for i in range(n):
        if move==0:
            if police[i][1]<=y:
                continue
            if police[i][1]-y>=abs(police[i][0]-x):
                return False
        elif move==1:
            if police[i][1]>=y:
                continue
            if y-police[i][1]>=abs(police[i][0]-x):
                return False
        elif move==2:
            if police[i][0]>=x:
                continue
            if x-police[i][0]>=abs(police[i][1]-y):
                return False
        else:
            if police[i][0]<=x:
                continue
            if police[i][0]-x>=abs(police[i][1]-y):
                return False
    return True

police=[]
for i in range(n):
    police.append(list(map(int,input().split())))
x,y=map(int,input().split())

for i in range(4):
    result=find(i)
    if result:
        break;
    
if result:
    print("YES")
else:
    print("NO")

 

기타

java 로 구현하기가 어려워서 먼저 파이썬으로 구현해보고 다시 java로 풀었다.

아이디어 자체는 어렵지 않은데 떠올리기가 어려웠다.