백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글

p21771 가희야 거기서 자는 거 아니야

처음 접근방법은 G의 각 꼭짓점 별로 좌표를 추적해서 좌우에 P가 있는지 탐색해보는 방식으로 접근했었는데, 정확한 이유는 모르겠지만 실패했다.

그래서 생각해 본 방법이 P의 넓이를 구하고 P의 갯수를 카운트했을 때 넓이가 안맞으면  가희가 베개를 사용하고 있는 것으로 판단하기로 해보고 문제를 풀어봤다.

hint

----

P의 갯수를 활용하는 것이 핵심

----

Solution

실행시간 - 124ms

import java.util.*;
import java.io.*;
 
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 r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int gr = Integer.parseInt(st.nextToken());
        int gc = Integer.parseInt(st.nextToken());
        int pr = Integer.parseInt(st.nextToken());
        int pc = Integer.parseInt(st.nextToken());
        
        char[][] map = new char[r][c];
        
        for(int i = 0; i < r; i++){
            map[i] = br.readLine().toCharArray();
        }
        
        int n = pr * pc; // 60
        int count = 0;
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(map[i][j] == 'P'){
                    count++;
                }
            }
        }
        
        if(count == n){
            System.out.println(0);
        }else{
            System.out.println(1);
        }
        
        
        
    }
    
    
}

 

다음에 기회가 된다면 각 꼭짓점 별로 판단하는 방식을 채용해보고 싶다... 정말 최고의 최적화일거같은데 반례가 어느걸까 궁금하다