잡기 놀이

문제

철수와 영희는 눈을 가리고 잡기 놀이를 하기로 했다.

철수는 도망치는 역할을 맡았으며, (x1, y1) 좌표에서 출발한다.

매 1초마다 철수는 동/서/남/북 중 한군데를 임의로 선택하여 이동한다.

영희는 철수를 잡는 역할을 맡았으며, (x2, y2) 좌표에서 출발한다.

매 1초마다 영희는 북서/북동/남서/남동 중 한군데를 임의로 선택하여 이동한다.

모든 경우 중에서, 영희가 철수를 가장 빨리 잡는 경우 몇 초의 시간이 걸리는지 출력하시오.

입력설명

• -1000 <= x1 <= 1000
• -1000 <= y1 <= 1000
• -1000 <= x2 <= 1000
• -1000 <= y2 <= 1000

출력설명

영희가 철수를 가장 빨리 잡았을 때의 소요 시간(초)를 정수로 출력

매개변수 형식

• x1 = 2
• y1 = 4
• x2 = 5
• y2 = -3

반환값 형식

4

예시 입출력 설명

아래와 같이 움직일 경우, 4초 후에 영희가 철수를 잡을 수 있다.

확인

 

풀이 방법

import java.util.*;

class Solution {
    public int solution(int x1, int y1, int x2, int y2) {
        Set<List<Integer>> setA = new HashSet<>();
        Set<List<Integer>> setB = new HashSet<>();
        setA.add(List.of(x1, y1));
        setB.add(List.of(x2, y2));

        Set<List<Integer>> historyA = new HashSet<>(Set.copyOf(setA));
        Set<List<Integer>> historyB = new HashSet<>(Set.copyOf(setB));

        if (x1 == x2 && y1 == y2) {
            return 0;
        }

        int time = 1;

        while (true) {
            Set<List<Integer>> newSetA = new HashSet<>();
            Set<List<Integer>> newSetB = new HashSet<>();

            setA.forEach(valA -> {
                newSetA.add(List.of(valA.get(0) + 1, valA.get(1)));
                newSetA.add(List.of(valA.get(0), valA.get(1) + 1));
                newSetA.add(List.of(valA.get(0) - 1, valA.get(1)));
                newSetA.add(List.of(valA.get(0), valA.get(1) - 1));
            });
            setB.forEach(valB -> {
                newSetB.add(List.of(valB.get(0) + 1, valB.get(1) + 1));
                newSetB.add(List.of(valB.get(0) - 1, valB.get(1) - 1));
                newSetB.add(List.of(valB.get(0) - 1, valB.get(1) + 1));
                newSetB.add(List.of(valB.get(0) + 1, valB.get(1) - 1));
            });

            newSetA.removeAll(historyA);
            newSetB.removeAll(historyB);

            for(List<Integer> posA : newSetA) {
                if(newSetB.contains(posA)) {
                    return time;
                }
            }

            historyA.addAll(newSetA);
            historyB.addAll(newSetB);

            setA = newSetA;
            setB = newSetB;
            time++;
        }
    }
}