🔍 문제
💻 제출
📌 입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)
각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).
다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)
송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)
📌 출력
각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.
📝 첫번째 코드(실패, 개념 오류)
package BFS;
import java.io.*;
import java.util.*;
public class Solution_9205 {
static int T, N;
static int SX,SY,FX,FY;
static LinkedList<Info> store = new LinkedList<>();
static class Info{
int x,y,d;
public Info(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine()); //테스트 케이스
for (int t = 0; t < T; t++) {
N = Integer.parseInt(br.readLine());
StringTokenizer stS = new StringTokenizer(br.readLine(), " ");
SX = Integer.parseInt(stS.nextToken()); //상근 x
SY = Integer.parseInt(stS.nextToken()); //상근 y
for (int i=0; i<N; i++){ //편의점
StringTokenizer stC = new StringTokenizer(br.readLine()," ");
int storeX = Integer.parseInt(stC.nextToken());
int storeY = Integer.parseInt(stC.nextToken());
int distance = Math.abs(storeX - SX) + Math.abs(storeY - SY);
store.offer(new Info(storeX,storeY,distance)); //편의점 좌표 저장
}
Collections.sort(store , (a,b)->(a.d - b.d)); //편의점 가까운 거리 정렬 , 람다
StringTokenizer stF = new StringTokenizer(br.readLine(), " ");
FX = Integer.parseInt(stF.nextToken()); //festival x
FY = Integer.parseInt(stF.nextToken()); //festival y
bw.write(bfs() ? "happy\n" : "sad\n");
}
bw.flush();
bw.close();
br.close();
}
static boolean bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {SX,SY}); //상근 집 좌표 입력
while (!q.isEmpty()){
int[] poll = q.poll();
int nowX = poll[0];
int nowY = poll[0];
int festivalD = Math.abs(FX - nowX) + Math.abs(FY - nowY);
//현재 지점 에서 festival 까지 거리
if (festivalD <= 1000){
return true; //festival 참여 가능
}
//현재 거리에서 참여 불가능 하다면 편의점 탐색
Info nextStore = store.removeFirst();
int nx = nextStore.x;
int ny = nextStore.y;
int storeD = Math.abs(nx - nowX) + Math.abs(ny - nowY);
if (storeD <= 1000){
q.offer(new int[] {nx,ny});
}
else{
return false;
}
}
return false;
}
}
위 코드를 작성하고 제출 했을 때 통과 되지 않아 한참 동안 고민 했었다.
예제는 통과 했기 때문에 반례 찾기도 쉽지는 않았다.
단순히 상근이와 festival 사이에 편의점이 배치 될 것 이라 생각 했어서 가까운 편의점 부터 정렬 한 후 차례차례 접근하면서 접근이 가능한 편의점을 지워주면서 진행하면 될 것이라 생각했다.
하지만 위와 같은 상황이 발생 한다면 편의점을 거리 순으로 정렬 하고 접근 할 것 이기 때문에 무조건 가까운 거리인 store1으로 접근 한다.
store1으로 접근 했다면 store2는 거리 간격이 1000M를 넘어가기 때문에 접근이 불가능 하다.
상근의 집에서 곧장 출발했다면 접근 가능했던 거리가 정렬 후 접근을 하게 됨으로써 꼬여버리는 것 이다.
📝 두번째 코드(정상 제출)
import java.io.*;
import java.util.*;
public class Main {
static int T, N;
static int SX, SY, FX, FY;
static ArrayList<Store> store;
static class Store {
int x, y;
public Store(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine()); //테스트 케이스
for (int t = 0; t < T; t++) {
N = Integer.parseInt(br.readLine());
StringTokenizer stS = new StringTokenizer(br.readLine(), " ");
SX = Integer.parseInt(stS.nextToken()); //상근 x
SY = Integer.parseInt(stS.nextToken()); //상근 y
store = new ArrayList<>();
for (int i = 1; i <= N; i++) { //편의점
StringTokenizer stC = new StringTokenizer(br.readLine(), " ");
int storeX = Integer.parseInt(stC.nextToken());
int storeY = Integer.parseInt(stC.nextToken());
store.add(new Store(storeX, storeY)); //편의점 좌표 저장
}
StringTokenizer stF = new StringTokenizer(br.readLine(), " ");
FX = Integer.parseInt(stF.nextToken()); //festival x
FY = Integer.parseInt(stF.nextToken()); //festival y
bw.write(bfs() ? "happy\n" : "sad\n");
}
bw.flush();
bw.close();
br.close();
}
static boolean bfs() {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{SX, SY}); //상근 집 좌표 입력
boolean visited[] = new boolean[store.size()];
while (!q.isEmpty()) {
int[] poll = q.poll();
int nowX = poll[0];
int nowY = poll[1];
long festivalD = Math.abs(FX - nowX) + Math.abs(FY - nowY);
//현재 지점 에서 festival 까지 거리
if (festivalD <= 1000) {
return true; //festival 참여 가능
}
//현재 거리에서 참여 불가능 하다면 편의점 탐색
int storeSize = store.size();
for (int i = 0; i < storeSize; i++) {
Store nextStore = store.get(i);
long storeD = Math.abs(nextStore.x - nowX) + Math.abs(nextStore.y - nowY);
if (visited[i] == false && storeD <= 1000) {
q.offer(new int[]{nextStore.x, nextStore.y});
visited[i] = true;
}
}
}
return false;
}
}
위 코드는 정상적인 BFS 를 통해서 상근의 집에서 festival 까지 모든 경로의 경우의 수에 접근 할 수 있다.
BFS를 사용한다면 어렵지 않게 풀 수 있는 문제다.
📗 정리
문제의 개념을 제대로 잡지 못하니 BFS ,DFS 등 알고리즘 자체가 필요 하지 않다 라고 판단 할 만큼 쉽다고 생각했다.
보통 문제를 풀기 까지 길어도 1시간이 걸리지 않기 때문에 오늘 마지막 문제를 풀고 깔끔하게 하루를 마무리 하려 했는데 자리에서 3시간을 넘게 사용했다.
새벽 4시가 가까워지는 지금 흐려지는 정신을 부여잡고 간단하게나마 문제에 대한 회고를 써보았다.
