프로그래머 340211번 충돌위험 찾기 Java

https://school.programmers.co.kr/learn/courses/30/lessons/340211

문제

---

생각하기

---

• 구현 문제이다.

• 로봇별 이동 경로를 시간 별로 기록해서 같은 시간, 같은 좌표에 있는 로봇들의 개수를 세면 된다.

동작

방향을 탐색할 때 BFS에서 하던 방식과 달랐다.

    private static List<Coordinate> makePath(Coordinate start, Coordinate end) {
        List<Coordinate> path = new ArrayList<>();
        int x = start.x;
        int y = start.y;

        // 경로 만들기
        while (x != end.x) {
            if (x < end.x) x++;
            else x--;
            path.add(new Coordinate(x, y));
        }

        while (y != end.y) {
            if (y < end.y) y++;
            else y--;
            path.add(new Coordinate(x, y));
        }

        return path;
    } // End of makePath()

어차피 상 하 좌 우 로 밖에 못 움직이면, 출발 장소와 도착 장소의 x값 차이를 기반으로 x먼저 움직이고, y를 움직이면 된다는 방식을 왜 생각하지 못했을까

결과

코드

---

Java

import java.util.*;

class Solution {
    private static class Coordinate {
        int x;
        int y;

        private Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Coordinate coordinate = (Coordinate) o;
            return x == coordinate.x && y == coordinate.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public String toString() {
            return "Coordinate{" + "x=" + x + ", y=" + y + '}';
        }
    } // End of Coordinate class

    public int solution(int[][] points, int[][] routes) {
        int ans = 0;

        Map<Integer, Coordinate> coordinateMap = new HashMap<>();
        int pointsLen = points.length;
        for (int i = 0; i < pointsLen; i++) {
            coordinateMap.put(i + 1, new Coordinate(points[i][0], points[i][1]));
        }

        List<List<Coordinate>> robotPaths = new ArrayList<>();

        for (int[] t : routes) {
            List<Coordinate> paths = new ArrayList<>();
            Coordinate start = coordinateMap.get(t[0]);

            paths.add(start);
            int tLen = t.length;

            for (int i = 1; i < tLen; i++) {
                Coordinate next = coordinateMap.get(t[i]);
                paths.addAll(makePath(start, next));
                start = next;
            }

            robotPaths.add(paths);
        }

        int maxTime = 0;
        for (List<Coordinate> paths : robotPaths) {
            maxTime = Math.max(maxTime, paths.size());
        }

        for (int i = 0; i < maxTime; i++) {
            Map<Coordinate, Integer> coordinateCount = new HashMap<>();

            for (List<Coordinate> path : robotPaths) {
                if (i < path.size()) {
                    Coordinate coord = path.get(i);
                    coordinateCount.put(coord, coordinateCount.getOrDefault(coord, 0) + 1);
                }
            }

            for (int count : coordinateCount.values()) {
                if (count > 1) {
                    ans++;
                }
            }
        }

        return ans;
    } // End of solution()

    private static List<Coordinate> makePath(Coordinate start, Coordinate end) {
        List<Coordinate> path = new ArrayList<>();
        int x = start.x;
        int y = start.y;

        // 경로 만들기
        while (x != end.x) {
            if (x < end.x) x++;
            else x--;
            path.add(new Coordinate(x, y));
        }

        while (y != end.y) {
            if (y < end.y) y++;
            else y--;
            path.add(new Coordinate(x, y));
        }

        return path;
    } // End of makePath()
} // End of Solution class

Kotlin

import java.util.*

class Solution {
    private data class Coordinate(val x: Int, val y: Int)
    
    fun solution(points: Array<IntArray>, routes: Array<IntArray>): Int {
        var ans = 0 
        val coordinateMap = HashMap<Int, Coordinate>()
        val pointsLen = points.size
        for (i in 0 until pointsLen) {
            coordinateMap[i + 1] = Coordinate(points[i][0], points[i][1])
        }


        val robotPaths: MutableList<MutableList<Coordinate>> = mutableListOf()
        for (t in routes) {
            val paths: MutableList<Coordinate> = mutableListOf()
            var start = coordinateMap[t[0]]
            paths.add(start!!)
            val tLen = t.size

            for (i in 1 until tLen) {
                val next = coordinateMap[t[i]]
                paths.addAll(makePath(start!!, next!!))
                start = next
            }
            robotPaths.add(paths)
        }

        var maxTime = 0
        robotPaths.forEach {
            maxTime = Math.max(maxTime, it.size)
        }


        for (i in 0 until maxTime) {
            val coordinateCount = HashMap<Coordinate, Int>()

            for (path in robotPaths) {
                if (i < path.size) {
                    val coor = path[i]
                    coordinateCount.put(coor, coordinateCount.getOrDefault(coor, 0) + 1)
                }
            }

            for (count in coordinateCount.values) {
                if (count > 1) ans++
            }
        }
        return ans
    } // End of solution()
    
    private fun makePath(start: Coordinate, end: Coordinate): MutableList<Coordinate> {
        val path: MutableList<Coordinate> = mutableListOf()

        var x = start.x
        var y = start.y

        while (x != end.x) {
            if (x < end.x) x++
            else x--
            path.add(Coordinate(x, y))
        }

        while (y != end.y) {
            if (y < end.y) y++
            else y--
            path.add(Coordinate(x, y))
        }

        return path
    } // End of makePath()
} // End of Solution class