백준 9205 - 맥주 마시면서 걸어가기

Java

9205 번 - 맥주 마시면서 걸어가기

문제

• 한번에 최대 1000m까지 갈 수 있으며, 도중에 편의점에 들러야 다시 1000m를 갈 수 있다.
• 페스티벌의 좌표에 도달 할 수 있으면 happy, 없으면 sad를 출력한다.

접근 방법

조지 플로이드 워셜의 문제이지만, 처음은 DFS로 해결하였다.

집의 좌표, n개의 편의점 좌표, 페스티벌의 좌표 순으로 총 n + 2개의 좌표를 저장한다.

집에서 부터 출발하여(0), n개의 편의점 좌표와 페스티벌의 좌표 중(1 ~ n + 1), 갈 수있는 모든 곳을 간다.
도착한 지점에서 1000m 이내의 갈 수 있는 좌표를 반복하여 탐색한다.

마지막으로 페스티벌의 좌표를 나타내는 n + 1 번째 좌표 방문 여부를 확인하여 방문했으면 happy를 출력한다.

코드

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

public class Main {
	static int n;
	static boolean[] vis;
	static Point[] p;
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk; 
    	int tc = stoi(br.readLine());
    	
    	for(int idx = 0; idx < tc; idx++) {
    		n = stoi(br.readLine());
    		
    		// 집 + 편의점 + 페스티벌 = n + 2
    		p = new Point[n+2];
    		vis = new boolean[n+2];
    		
    		for(int i = 0; i < n + 2; i++) {
    			stk = new StringTokenizer(br.readLine());
    			p[i] = new Point(stoi(stk.nextToken()),stoi(stk.nextToken()));
    		}
    		
    		vis[0] = true;
    		DFS(p[0]);
    		
    		if(vis[n+1])
    			System.out.println("happy");
    		else
    			System.out.println("sad");
    	}
    	
    	br.close();
    }
    
    private static void DFS(Point curP) {
		
		for(int i = 1; i < n + 2; i++) {
			// 편의점과 페스티벌 중 어디든 1000m 이내로 갈 수 있을 시
			if(!vis[i] && chkDis(p[i], curP)) {
				vis[i] = true;
				DFS(p[i]);
			}
		}
	}
    
    static boolean chkDis(Point a, Point b) {
    	int distance = Math.abs(a.y - b.y) + Math.abs(a.x - b.x);
    	
    	if(distance <= 1000) {
    		return true;
    	}
    	return false;
    }

	static class Point{
    	int y,x;

		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("[").append(y).append(", ").append(x).append("]");
			return builder.toString();
		}

		public Point(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
    }
    
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

결론적으로 이 문제는 해결하지 못하고 솔류션을 보았다.

실패 요인은 한번 방문한 장소를 다시 방문하지 않았다는 vis[i] = false로 초기화하여 100!의 시간 복잡도를 유발하였다.

결국 이 문제는 해당하는 지점에 갈 수 있는지 여부만을 알아내는 문제이므로,
DFS의 개념인 깊이 우선 탐색으로 페스티벌에 갈 수 있다면 결국 도달한다.
즉, 가지가 뻗어나간다고 생각하고 그 가지의 끝이 페스티벌이 있는지 아닌지 확인만 하면 된다.

vis[i] = false은 특정 지점에 도달하는 경로를 확인할 때(가중치) 어떻게 가는지 확인 할때 방문 여부를 초기화 하는 것이다.

개선할 점

실패로 배워나가자