Point 💡

• 수학적으로만 계산 → 문제 발생
  • 상근, 편의점1, 편의점2, 페스티벌의 위치가 순서대로 위치에 있을거라는 보장이 없다.
  • 상근 - 페스티벌 위치가 편의점을 들리지않아도(맥주를 구매하지않아도) 갈 수 있다면, 편의점을 들리지 않아도 된다.

How?

모든 정점을 탐색해서 가능한 경우가 있으면 happy를 바로 출력한다. BFS 또는 DFS를 이용하자!

My Solution

Incorrect Code

import sys
t = int(sys.stdin.readline())

coordinates = []
happy_flag = True
for _ in range(t):
    n = int(sys.stdin.readline())
    current = 20
    for _ in range(n+2):
        coordinates.append(tuple(map(int, sys.stdin.readline().split())))

    for i in range(1, len(coordinates)):
        diff = abs(coordinates[i][0] - coordinates[i-1][0]) + abs(coordinates[i][1] - coordinates[i-1][1])
        drank_beer = diff // 50

        if drank_beer >= 20 and diff % 50 != 0:
            happy_flag = False
            break

        current -= drank_beer

        if i != len(coordinates) -1 :
            current += drank_beer

    if happy_flag:
        print("happy")
    else:
        print("sad")

• 반례

  1
  2
  0 0
  1000 0
  2000 1000
  1000 1000
  

Correct Code : BFS

python

import sys
from collections import deque 

def bfs():
    queue = deque()
    queue.append((home_x, home_y))

    while queue:
        # 편의점을 들리지않고, 바로 페스티벌로 갈 수 있다면
        x, y = queue.popleft()
        if abs((festival_x - x)) + abs((festival_y - y)) <= 1000:
            print("happy")
            return

        # 편의점을 들러야한다면 모든 편의점 방문한 후
        for i in range(n):
            # 그 편의점을 방문하지않았다면
            if not visited[i]:
                new_x, new_y = convenience_stores[i]
                if abs((new_x - x)) + abs((new_y - y)) <= 1000:
                    visited[i] = 1
                    queue.append((new_x, new_y))

    print("sad")
    return

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    convenience_stores = []

    # 시작 지점은 정해져있음
    home_x, home_y = map(int, sys.stdin.readline().split())
    for _ in range(n):
        convenience_stores.append(tuple(map(int, sys.stdin.readline().split())))

    festival_x, festival_y = map(int, sys.stdin.readline().split())

    # 방문한 편의점 확인
    visited = [0 for _ in range(n+1)]
    bfs()

java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int t, n, homeX, homeY, festivalX, festivalY;
	static List<int[]> convenienceStores;
	static int[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = null;
		t = Integer.parseInt(br.readLine());

		for (int i = 1; i <= t; i++) {
			n = Integer.parseInt(br.readLine());
			convenienceStores = new ArrayList<>();

			st = new StringTokenizer(br.readLine());
			homeX = Integer.parseInt(st.nextToken());
			homeY = Integer.parseInt(st.nextToken());

			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(br.readLine());
				convenienceStores.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
			}

			st = new StringTokenizer(br.readLine());
			festivalX = Integer.parseInt(st.nextToken());
			festivalY = Integer.parseInt(st.nextToken());

			visited = new int[n];
			Arrays.fill(visited, 0);

			bw.write(bfs() ? "happy\\n" : "sad\\n");
		}

		// bw flush, close 해줘야함.
		bw.flush();
		bw.close();
	}

	static boolean bfs() {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[]{homeX, homeY});

		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int x = cur[0], y = cur[1];
			if (Math.abs(festivalX - x) + Math.abs(festivalY - y) <= 1000) {
				return true;
			}

			for (int i=0; i<n ; i++){
				if (visited[i] == 0) {
					int newX = convenienceStores.get(i)[0], newY = convenienceStores.get(i)[1];
					if (Math.abs(newX - x) + Math.abs(newY - y) <= 1000) {
						visited[i] = 1;
						q.add(new int[]{newX, newY});
					}
				}
			}
		}
		return false;
	}

}