문제 이해

맥주 1병을 마시면 50m를 갈 수 있다.
처음에 출발할 때는 맥주를 20병 가져간다.

중간에 편의점이 존재하는데 편의점에서 맥주를 팔고 있어서 보충이 가능하다.
하지만, 보유 맥주는 20개를 넘을 수 없다.(20개 이하만 보유 가능)

집에서 출발하여 목적지까지 도착할 수 있을지를 출력하는 문제이다.

---

문제 풀이

50m를 가려면 맥주 1병을 마셔야 한다.
즉, 20병을 다마신다고 가정했을 때 상근이와 친구들은 총 1000m를 이동할 수 있는 것이다.

따라서, 한 번 이동할 때 무조건 1000m를 움직인다고 가정하여 편의점에 들르면서 목적지에 도착할 수 있으면 "happy"를, 1000m씩 움직이는 걸로는 목적지에 도달할 수 없다면 "sad"를 출력하면 된다.

---

코드

JAVA

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

class Point {
	int x;
	int y;
	
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	@Override
	public boolean equals(Object o) {
		Point p = (Point) o;
		return this.x==p.x && this.y==p.y;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static Point start;
    static Point end;
    
	static ArrayList<Point> points;
	static ArrayList<Integer>[] lists;
    // lists[i] : i번째 Point에서 갈 수 있는 지점들
    
	static int N;
	
	static int distance(Point p1, Point p2) {
		return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
	}
	
	static void dfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(0);
		boolean[] visit = new boolean[N+2];
		
		while(!queue.isEmpty()) {
			int p = queue.poll();
			
			if(p == N + 1) {
            // 목적지에 도달 한 상황
            // Happy를 출력하고 종료한다.
				sb.append("happy\n");
				return;
			}
			
			visit[p] = true;
            // 해당 Point를 재방문하는 것은 고려할  필요가 없는 상황
            // 따라서, visit[p] = true로 만들고, 재방문하는 상황을 제거한다.
            
			for(int i = 0;i<lists[p].size();i++) {
				int tmp = lists[p].get(i);
				if(!visit[tmp]) {
                // 이전에 방문해보지 못한 편의점 or 도착지
                // 따라서, Queue에 더해주고 방문했다는 것을 명시함
					queue.add(tmp);
					visit[tmp] = true;
				}
			}
		}

		sb.append("sad\n");
        // While문이 종료될 때 까지 return이 시행되지 않았다
        // 즉 p==N+1인 상황이 없었다는 의미이므로 도착할 수 없는 상황인 것이다
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int T = sc.nextInt();
		
		for(int t=0;t<T;t++) {
			N = sc.nextInt();
			
			points = new ArrayList<Point>();
			
			start = new Point(sc.nextInt(), sc.nextInt());
			points.add(start);
			
			for(int i =0;i<N;i++) {
				points.add(new Point(sc.nextInt(), sc.nextInt()));
			}
			
			end = new Point(sc.nextInt(), sc.nextInt());
			points.add(end);
            // start는 point의 0번째 Index, end는 N+1번째 Index에 존재함
			
			lists = new ArrayList[N+2];
			
			for(int i =0;i<N+2;i++) {
				lists[i] = new ArrayList<>();
			}
			
			for(int i =0;i<N+1;i++) {
				for(int j =i+1;j<N+2;j++) {
					if(distance(points.get(i), points.get(j))<=1000) {
                    // i번째 지점에서 j번째 지점까지 1000m 이하의 거리를 가진다
                    // 즉, 갈 수 있는 거리라는 뜻이므로 lists에 추가해준다.
						lists[i].add(j);
						lists[j].add(i);
					}
				}
			}
			
			dfs();
		}
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

Python

import sys
from collections import deque

def bfs():
    q = deque()
    q.append([home[0], home[1]])
    while q:
        x, y = q.popleft()
        if abs(x - fest[0]) + abs(y - fest[1]) <= 1000:
            print("happy")
            return
        for i in range(n):
            if not visited[i]:
                new_x, new_y = lists[i]
                if abs(x - new_x) + abs(y - new_y) <= 1000:
                    q.append([new_x, new_y])
                    visited[i] = 1
    print("sad")
    return

t = int(input())
for i in range(t):
    n = int(input())
    home = [int(x) for x in input().split()]
    lists = []
    for j in range(n):
        x, y = map(int, input().split())
        lists.append([x, y])
    fest = [int(x) for x in input().split()]
    visited = [0 for i in range(n+1)]
    bfs()

---

결과

• 컴파일 에러 : Python 코드를 JAVA로 실행시켰었다

• 메모리 초과
  Point Class에 지점 사이의 거리까지 저장시켰는데, 이렇게 되니 메모리 초과가 발생했다.
  (i,j)가 Queue에 많이 들어갔을 경우 똑같은 Point가 Queue에 중복으로 들어가 있다보니 메모리가 부족해진 것 같다

• 틀렸습니다 : 1000m가 아닌 50m 기준으로 코드를 짰었는데, 그러다보니 세세한 부분까지 모두 신경써야 해서 놓친 부분이 존재했던 것 같다