문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

---

Python

from sys import stdin

t=int(stdin.readline().strip())
result=[]

def distance(a, b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])

for _ in range(t):
    grocery_num=int(stdin.readline().strip())
    house=[int(i) for i in stdin.readline().strip().split()]
    grocery=list(enumerate(list(map(int, stdin.readline().strip().split())) for _ in range(grocery_num)))
    visited=[0]*len(list(grocery))
    festival=[int(i) for i in stdin.readline().strip().split()]
    is_happy=0

    q=[(0, house), ]
    while q:
        current=q.pop()
        if distance(festival, current[1])<=1000:
            is_happy=1
            break

        grocery=[i for i in grocery if not visited[i[0]]]
        for i in grocery:
            if distance(i[1], current[1])<=1000:
                visited[i[0]]=1
                q.append(i)

    result.append(is_happy)

for i in result:
    print("happy") if i else print("sad")

Java

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

class Main{
    public static int distance(int[] a, int[] b){
        return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            int groceryNum=Integer.parseInt(br.readLine());

            StringTokenizer st=new StringTokenizer(br.readLine());
            int[] house={Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            LinkedList<int[]> grocery=new LinkedList<>();
            for(int i=0; i<groceryNum; i++){
                st=new StringTokenizer(br.readLine());
                grocery.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
            }

            st=new StringTokenizer(br.readLine());
            int[] festival={Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            boolean isHappy=false;

            Stack<int[]> s=new Stack<>();
            s.add(house);
            while(!s.isEmpty()){
                int[] current=s.pop();
                if(distance(current, festival)<=1000){
                    isHappy=true;
                    break;
                }

                Iterator<int[]> nodes=grocery.listIterator();
                while(nodes.hasNext()){
                    int[] node=nodes.next();
                    if(distance(node, current)<=1000){
                        nodes.remove();
                        s.push(node);
                    }
                }
            }
            bw.write((isHappy)? "happy\n" : "sad\n");
        }
        bw.flush();
    }
}

---

해결 과정

1. 굳이 모든 노드를 탐색할 필요 없이 DFS를 사용해서 목표 지점에 도착하면 끝내는 것이 빠르다고 생각했다.

2. 처음에는 집과 페스티벌의 xy 좌표계 사이에 있는 편의점만 거치면서 가는 쪽으로 생각했다. 하지만 밖으로 돌아서 가는 길이 존재할 수도 있으므로 전체 노드에 대해서 탐색하기로 했다.

3. 다음 노드를 찾기 위해서 grocery 배열을 탐색하는데 매번 모든 편의점을 탐색하면 느리므로 방문한 편의점에 대해서는 제외시켜줬다. 해당 노드에 방문할 수 있는지가 중요하므로 (편의점A -> 편의점C) 인지 (편의점B -> 편의점C) 인지는 의미없다.

4. 😁