[백준 / BOJ] 1445 일요일 아침의 데이트 (Java)

문제

출처 : https://www.acmicpc.net/problem/1445

1445번: 일요일 아침의 데이트

형택이는 여자친구와 데이트를 하려고한다. 자신의 여자친구는 쓰레기를 지나가는것과, 쓰레기 주위를 지나가는것을 굉장히 싫어하기 때문에, 형택이는 이러한 상황을 최대한 피하고자한다.

 

숲의 크기 n,m 쓰레기의 위치(g), 형택이의 위치(S), 도착위치(F)가 주어진다.

이때, 위와 같은 상황을 최소화 하여 움직였을때 쓰레기를 지나간 횟수와 쓰레기 주위를 지나간 횟수를 출력하는 프로그램을 만드는 문제다.

 

풀이

문제는 어렵지 않았으나 (익숙하지않은 언어와) 문제 해석이 어려웠던 문제다.

 

다익스트라로 풀은 문제다.

 

로직은 다음과 같다.

priorityQueue를 선언후, {쓰레기를 밟고지나간횟수, 쓰레기 옆을 지나간 횟수, y, x}형태로 저장해가며 기본 다익스트라를 수행하면 된다.

+ check배열또한 {쓰레기를 밟고지나간횟수, 쓰레기 옆을 지나간횟수} 형태로 저장해가며 비교해줘야하는것에 주의하자.

(출력은 쓰레기를 밟고지나간횟수를 가장적게 해야하며 이때, 쓰레기 옆을 지나간횟수가 적은것을 출력해야하니..)

 

문제는 문제의 해석이 어렵다는것인데, 모호한 설명들을 아래에 정리해놓겠다.

(아마 대부분 이 이유때문에 게시글을 읽고있을거라 생각한다..)

 

1.  "쓰레기 옆을 지나가는 칸의 개수를 최소로 해서 지나려고 한다."

- 쓰레기 옆이라는것은 상,하,좌,우 만 뜻한다. 대각선은 카운트하지않는다.

- 또한, 한 칸(y,x)를 지나갈때 주위에 쓰레기가 2개이상 있더라도, 쓰레기 주위를 지나간 칸은 한개이다. (쓰레기가 주위에 몇개가 있더라도 쓰레기 주위를 지나간 칸은 하나임.)

 

2. "만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다." (반례 제조 문장이였다.)

- 위 문장때문에, 형택이의 시작위치인 S와 꽃이있는위치인 F는 카운트하지않는다.(결국 S와 F또한 비어있는칸이 아니다. 자세한 설명은 아래 링크를 참조하자.)

https://www.acmicpc.net/board/view/67948

 

- 위 문장은 쓰레기 에도 그대로 적용된다. 예를들어, 임의의 위치 (y,x)에 쓰레기 g가 있고, (y,x)주위 4방향에 g가 있는 상황있다고 가정하자. 이 때, (y,x)를 지나치더라도 쓰레기 주위를 지나간것은 아니다.(y,x)가 비어있는칸이 아닌 쓰레기가 있는칸이므로.

 

Java로 구현할려하니까, Pair등 여러가지를 직접 구현해서 써야했다.... PriorityQueue에 넣어서 쓸려면 (우선순위 큐는 정렬할때 내부적으로 compareTo메소드를 사용하기때문에, 정렬하기위해 Comparable 인터페이스를 구현해야한다.) 

 

아래는 PriorityQueue에 넣기위해 직접 구현한 클래스이다.

class Position implements Comparable<Position>{
    public int garbageCnt, sideCnt, y, x;
    public Position(int garbageCnt, int sideCnt, int y, int x){
        this.garbageCnt = garbageCnt;
        this.sideCnt = sideCnt;
        this.y = y;
        this.x = x;
    }
    
    @Override
    public int compareTo(Position pos){
        if(this.garbageCnt > pos.garbageCnt) return 1;
        if(this.garbageCnt < pos.garbageCnt) return -1;
        if(this.garbageCnt == pos.garbageCnt) {
            if(this.sideCnt > pos.sideCnt) return 1;
            if(this.sideCnt < pos.sideCnt) return -1;
        }
        return 0;
    }
    
}

 

Comparable인터페이스의 CompareTo를 구현하여 비교해준다..

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1445%20%EC%9D%BC%EC%9A%94%EC%9D%BC%20%EC%95%84%EC%B9%A8%EC%9D%98%20%EB%8D%B0%EC%9D%B4%ED%8A%B8/Main.java

devxb/JJUNalgo