[코드트리] 자동 잔디 깎이 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/automatic-lawn-mowing?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

어마어마하게 빨리 자라는 잔디를 자동으로 깎는 기계가 있습니다. 이 기계는 정확한 프로그래밍으로 인해 잔디를 깎은 자리를 기계가 다시 방문했을 때는 이미 어느 정도 다시 자라서 깎을 거리가 항상 있습니다. 이 잔디 깎는 기계가 움직이는 방향과 이동한 거리의 기록이 총 N번 주어지며, 기계는 1초마다 거리 1 만큼씩 움직입니다. 기록을 참고해 잔디를 깎고 나서 재 방문 시 항상 다시 깎을 거리가 생기도록 하는 최소 주기를 구하는 프로그램을 작성해 보세요.

 

이 기계는 0에서 출발하여 7초에 지났던 곳을 17초에 다시 지나가게 되며, 2초에 지났던 곳을 26초에 다시 지나가게 됩니다. 이것은 10초 안에는 동일한 위치에 다시 잔디가 자라서 깎을 거리가 생겨야만 함을 뜻합니다. 따라서 잔디가 자라 재 방문시 항상 깎을거리가 생기는 최소 주기는 10초입니다.

 

입력 예시

6
N 10
E 2
S 3
W 4
S 5
E 8

 

출력 예시

10

 

 

코드

첫 번째 줄에 정수 N이 주어집니다.

두 번째 줄부터는 N개의 줄에 걸쳐 각 줄마다 이동방향과 이동한 거리가 공백을 사이에 두고 주어집니다. 방향은 W, S, N, E 중에 하나이며 각각 서, 남, 북, 동쪽으로 이동함을 의미합니다.

• 1 ≤ N ≤ 100
• 1 ≤ 기계가 한 번에 움직이는 거리 ≤ 10

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

public class Main {
    // 좌표와 시간을 담은 노드(잔디 깎이가 지나간 정보)
    static class Node {
        int x;
        int y;
        int time;

        public Node(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    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;
        int n = Integer.parseInt(br.readLine());
        // 잔디 좌표와 시간을 담을 리스트
        List<Node> nodeList = new ArrayList<>();
        int x = 0;
        int y = 0;
        int time = 0;
        int result = Integer.MAX_VALUE; // 결과를 담을 변수

        // 입력 받기
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String direction = st.nextToken(); // 방향
            int distance = Integer.parseInt(st.nextToken()); // 거리

            // 방향에 따른 이동 좌표와 시간을 가진 노드 생성 후 리스트에 담기
            for (int j = 0; j < distance; j++) {
                time++;

                if (direction.equals("E")) {
                    x++;
                    nodeList.add(new Node(x, y, time));
                }

                if (direction.equals("W")) {
                    x--;
                    nodeList.add(new Node(x, y, time));
                }

                if (direction.equals("S")) {
                    y--;
                    nodeList.add(new Node(x, y, time));
                }

                if (direction.equals("N")) {
                    y++;
                    nodeList.add(new Node(x, y, time));
                }
            }
        }
        br.close();

        // nodeList 순회
        for (int j = 0; j < nodeList.size(); j++) {
            Node currentNode = nodeList.get(j);

            // 현재 노드와 같은 위치에 있는 노드 찾기
            for (int k = j + 1; k < nodeList.size(); k++) {
                Node tempNode = nodeList.get(k);
                if (currentNode.x == tempNode.x && currentNode.y == tempNode.y) {
                    // 현재 노드의 시간 - 비교 노드의 시간
                    result = Math.min(result, Math.abs(currentNode.time - tempNode.time));
                }
            }
        }

        // 같은 위치에 있는 노드가 존재하지 않는 경우
        if (result == Integer.MAX_VALUE) {
            result = -1;
        }

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
}