[JAVA] 다익스트라 알고리즘 뿌수기3

 

 

2151 거울 설치 - 골드3

https://www.acmicpc.net/problem/2151

2151번: 거울 설치

 

진짜 감도 안잡혀서 구글링 후 답을 봤는데도 납득이 안간다

이 경우에 답이 나와야하는데, 다른 사람들이 올린 정답코드는 왜 이 경우를 고려하지않을까?

거울 반사각을 생각하면 대각선의 경우도 고려해야하는 게 아닌가? 짜증난다

 

다른 사람의 풀이를 보면 그냥 수직/ 수평만 고려하고, 반사하는 경우 90도 꺾기만 한다.

문제 어디에 수직/수평으로만 진행된다고되어있나?

빛이 수직수평으로만 진행된다면 간단하게 bfs로 풀 수 있을 듯

 

public class Main {
    static int size;
    static boolean[][][] visit;
    static char[][] arr;
    static int[] rowStep = new int[]{-1,0, 1, 0};
    static int[] colStep = new int[]{0,-1, 0, 1}; //위 좌 아래 우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(br.readLine());

        arr = new char[size][size];
        List<int[]> doors = new ArrayList<>();

        for (int i =0; i<size; i++) {
            String input = br.readLine();
            for (int j=0; j<size; j++) {
                arr[i][j] = input.charAt(j);
                if (arr[i][j] == '#') {
                    doors.add(new int[]{i, j});
                }
            }
        }

        int[] firstDoor = doors.get(0);
        arr[firstDoor[0]][firstDoor[1]] = '*';

        System.out.println(bfs(firstDoor));
    }

    private static int bfs(int[] firstDoor) {
        PriorityQueue<Direction> pq = new PriorityQueue<>();

        for (int i =0; i<4; i++) {
            int tmpRow = firstDoor[0] + rowStep[i];
            int tmpCol = firstDoor[1] + colStep[i];

            if (tmpRow >= 0 && tmpRow < size && tmpCol >= 0 && tmpCol < size && arr[tmpRow][tmpCol] != '*') {
                pq.add(new Direction(i, new int[]{tmpRow, tmpCol}, 0));
            }
        }

        visit = new boolean[size][size][4];
        for (int i =0; i<4; i++) {
            visit[firstDoor[0]][firstDoor[1]][i] = true;
        }

        while (!pq.isEmpty()) {
            Direction current = pq.poll();
            int[] loc = current.location;
            visit[loc[0]][loc[1]][current.dir] = true;

            if (arr[loc[0]][loc[1]] == '#') {
                return current.count;
            }

            if (arr[loc[0]][loc[1]] == '!') {
                int dir = (current.dir + 1)%4;
                if (visit[loc[0]][loc[1]][dir] == false) {
                    pq.add(new Direction(dir, new int[]{loc[0], loc[1]}, current.count+1));
                }

                dir = (current.dir + 3)%4;
                if (visit[loc[0]][loc[1]][dir] == false) {
                    pq.add(new Direction(dir, new int[]{loc[0],loc[1]}, current.count+1));
                }
            }

            int tmpRow = loc[0] + rowStep[current.dir];
            int tmpCol = loc[1] + colStep[current.dir];

            if (tmpRow >= 0 && tmpRow < size && tmpCol >= 0 && tmpCol < size
                    && visit[tmpRow][tmpCol][current.dir] == false
                    && arr[tmpRow][tmpCol] != '*'
            ) {
                pq.add(new Direction(current.dir, new int[]{tmpRow, tmpCol}, current.count));
            }
        }

        return 0;
    }
}

class Direction implements Comparable<Direction>{
    int dir;
    int count;
    int[] location;

    public Direction(int dir, int[] location, int count) {
        this.dir = dir;
        this.location = location;
        this.count = count;
    }

    @Override
    public int compareTo(Direction o) {
        return count - o.count;
    }
}

• 이 문제를 풀고 다익스트라나 bfs나 별 차이 없다는 걸 느꼈다
  • 둘의 차이는 PriorityQueue를 쓰냐 안쓰냐 차이인듯
• bfs를 잘 못해서 어렵게 풀었다

 

 

 

6087 레이저 통신 - 골드3

https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

• 이전 거울문제처럼 90도 회전시킨다고 한다
• 위아래만 판단할거다. 또 bfs로 풀면 될듯

 

class Location {
    int row;
    int col;

    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

class Value implements Comparable<Value> {
    int dir;
    int count;
    Location loc;

    public Value(int dir, int count, Location loc) {
        this.dir = dir;
        this.count = count;
        this.loc = loc;
    }

    @Override
    public int compareTo(Value o) {
        return count - o.count;
    }
}

public class Main {
    static int[] rowStep = new int[]{-1, 0, 1, 0};
    static int[] colStep = new int[]{0, -1, 0, 1};
    static char[][] arr;
    static Location start;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int width = Integer.parseInt(st.nextToken());
        int height = Integer.parseInt(st.nextToken());

        arr = new char[height][width];

        for (int i =0; i<height; i++) {
            String input = br.readLine();
            for (int j =0; j<width; j++) {
                arr[i][j] = input.charAt(j);
                if (arr[i][j] == 'C') {
                    start = new Location(i, j);
                }
            }
        }

        arr[start.row][start.col] = '*';
        bfs(start);
    }

    private static void bfs(Location start) {
        PriorityQueue<Value> pq = new PriorityQueue<>();
        boolean[][][] visit = new boolean[arr.length][arr[0].length][4];

        for (int i =0; i<4; i++) {
            visit[start.row][start.col][i] = true;
        }

        for (int i =0; i<4; i++) {
            int tmpRow = start.row + rowStep[i];
            int tmpCol = start.col + colStep[i];

            if (isValidLocation(tmpRow, tmpCol)) {
                if (arr[tmpRow][tmpCol] != '*') {
                    pq.add(new Value(i, 0, new Location(tmpRow, tmpCol)));
                }
            }
        }

        while (!pq.isEmpty()) {
            Value value = pq.poll();
            Location current = value.loc;

            if (!visit[current.row][current.col][value.dir]) {
                visit[current.row][current.col][value.dir] = true;

                if (arr[current.row][current.col] == 'C') {
                    System.out.println(value.count);
                    break;
                }

                int tmpDir = (value.dir + 1) % 4;
                pq.add(new Value(tmpDir, value.count+1, current));

                tmpDir = (value.dir + 3) % 4;
                pq.add(new Value(tmpDir, value.count+1, current));

                int tmpRow = current.row + rowStep[value.dir];
                int tmpCol = current.col + colStep[value.dir];
                if (isValidLocation(tmpRow, tmpCol)) {
                    if (arr[tmpRow][tmpCol] != '*' && !visit[tmpRow][tmpCol][value.dir]) {
                        pq.add(new Value(value.dir, value.count, new Location(tmpRow, tmpCol)));
                    }
                }
            }
        }
    }

    private static boolean isValidLocation(int row, int col) {
        if (row >= 0 && row < arr.length && col >= 0 && col < arr[0].length) {
            return true;
        }

        return false;
    }
}

• 거울 문제를 풀고나니 다시 풀기 어렵지 않다 - 유형을 알아야하는듯
• 코드를 좀 더 깔끔하게 짠 느낌! 발전했당

 

 

 

9694 무엇을 아느냐가 아니라 누구를 아느냐.. - 골드3

https://www.acmicpc.net/problem/9694

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

• 굉장히 쉬운 다익스트라문제다
• 이전 노드만 잘 저장해주면 될듯(다음 노드는 변경될 여지가 많으니까 이전노드를 저장해뒀다)
  • 플루이드는 다음노드를 저장함(차이점 발견했다!)

 

class Node implements Comparable<Node> {
    int intimacy;
    int end;

    public Node(int intimacy, int end) {
        this.intimacy = intimacy;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return intimacy - o.intimacy;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc<=tcCnt; tc++) {
            st = new StringTokenizer(br.readLine());
            int relationCnt = Integer.parseInt(st.nextToken());
            int politicianCnt = Integer.parseInt(st.nextToken());

            arr = new ArrayList[politicianCnt];
            for (int i =0; i<arr.length; i++) {
                arr[i] = new ArrayList<>();
            }

            for (int i =0; i<relationCnt; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int intimacy = Integer.parseInt(st.nextToken());

                arr[a].add(new Node(intimacy, b));
                arr[b].add(new Node(intimacy, a));
            }

            sb.append("Case #"+tc+": " + dijkstra(politicianCnt, 0, politicianCnt-1) + "\n");
        }

        System.out.print(sb);
    }

    private static String dijkstra(int politicianCnt, int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, start));

        boolean[] visit = new boolean[politicianCnt];
        int[] intimacies = new int[politicianCnt];
        int[] prev = new int[politicianCnt];
        Arrays.fill(intimacies, Integer.MAX_VALUE);

        intimacies[start] = 0;
        prev[start] = start;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (!visit[curr]) {
                visit[curr] = true;


                for (Node adj: arr[curr]) {
                    if (!visit[adj.end] && intimacies[adj.end] > intimacies[curr] + adj.intimacy) {
                        intimacies[adj.end] = intimacies[curr] + adj.intimacy;
                        prev[adj.end] = curr;
                        pq.add(new Node(intimacies[adj.end], adj.end));
                    }
                }
            }
        }

        if (intimacies[end] == Integer.MAX_VALUE) {
            return "-1";
        }

        Stack<Integer> stack = new Stack<>();
        int tmp = end;
        while(true) {
            stack.push(tmp);
            if (prev[tmp] == tmp) {
                break;
            }
            tmp = prev[tmp];
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }

        return sb.toString();
    }
}

• 정말 그냥 다익스트라다
• prev 배열만 달라짐

 

 

 

11779 최소비용 구하기 2 - 골드3

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

• 제목부터 다익스트라 냄새 무엇
• 경로를 구하는 게 포인트인듯
• 테케랑 답이 달랐지만 내 답이 맞다는 생각으로 그냥 제출했더니 통과됨 ㅎ.. 여러 개의 정답도 허용해주는듯

 

class Node implements Comparable<Node> {
    int end;
    int value;

    public Node(int end, int value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

public class Main {
    static ArrayList<Node>[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int countryCnt= Integer.parseInt(br.readLine());
        int busCnt= Integer.parseInt(br.readLine());

        arr = new ArrayList[countryCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<busCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int cost = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(b, cost));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken())-1;
        int end = Integer.parseInt(st.nextToken())-1;

        dijkstra(start, end);
    }

    private static void dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        boolean[] visit = new boolean[arr.length];
        int[] prev = new int[arr.length];
        int[] value = new int[arr.length];
        Arrays.fill(value, Integer.MAX_VALUE);
        value[start] = 0;
        prev[start] = start;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (!visit[curr]) {
                visit[curr] = true;

                if (curr == end) {
                    break;
                }

                for (Node adj: arr[curr]) {
                    if (!visit[adj.end] && value[adj.end] > value[curr] + adj.value) {
                        value[adj.end] = value[curr] + adj.value;
                        prev[adj.end] = curr;
                        pq.add(new Node(adj.end, value[adj.end]));
                    }
                }
            }
        }

        Stack<Integer> stack = new Stack<>();
        int num = end;
        while (true) {
            stack.push(num);
            if (num == start) {
                break;
            }
            num = prev[num];
        }

        StringBuilder sb = new StringBuilder();
        sb.append(value[end] + "\n");
        sb.append(stack.size() + "\n");
        while (!stack.isEmpty()) {
            sb.append(stack.pop()+1 + " ");
        }

        System.out.println(sb);
    }
}

• 설명할 게 없는 다익스트라 문제

 

 

 

14431 소수마을 - 골드3

https://www.acmicpc.net/problem/14431

14431번: 소수마을

• 내가 자신없는 소수가 나왔다..
• 갈 수 있는 마을을 소수인지 판별해서 결정하는 것 외에는 딱히 어려운 것이 없었다

 

class Location {
    int x;
    int y;

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

class Node implements Comparable<Node> {
    int end;
    int value;

    public Node(int end, int value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

public class Main {
    static Location[] country;
    static ArrayList<Node>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        Location start = new Location(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        Location end = new Location(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        int countryCnt = Integer.parseInt(br.readLine());

        country = new Location[countryCnt+2];

        for (int i =0; i<countryCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            country[i] = new Location(x, y);
        }

        country[countryCnt] = start;
        country[countryCnt+1] = end;

        arr = new ArrayList[countryCnt+2];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<country.length-1; i++) {
            Location country1 = country[i];
            for (int j =1; j<country.length; j++) {
                Location country2 = country[j];
                int sqrt = (int) Math.sqrt(Math.pow(country1.x - country2.x, 2) + Math.pow(country1.y - country2.y, 2));
                if (isPrime(sqrt)) {
                    arr[i].add(new Node(j, sqrt));
                    arr[j].add(new Node(i, sqrt));
                }
            }
        }

        dijkstra(countryCnt, countryCnt+1);
    }

    private static void dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        boolean[] visit = new boolean[arr.length];
        int[] values = new int[arr.length];
        Arrays.fill(values, Integer.MAX_VALUE);
        values[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (!visit[current]) {
                visit[current] = true;

                if (current == end) {
                    break;
                }

                for (Node adj: arr[current]) {
                    if (!visit[adj.end] && values[adj.end] > values[current] + adj.value) {
                        values[adj.end] = values[current] + adj.value;
                        pq.add(new Node(adj.end, values[adj.end]));
                    }
                }
            }
        }

        if (values[end] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(values[end]);
        }
    }

    private static boolean isPrime(int sqrt) {
        if (sqrt <= 1) {
            return false;
        }

        for (int i =2; i<=(int)Math.sqrt(sqrt); i++) {
            if (sqrt % i == 0) {
                return false;
            }
        }

        return true;
    }
}

 

 

 

2211 네트워크 복구 - 골드2

https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

• 스패셜 저지인 걸 보니 새로운 알고리즘이 있는건지 무서워졌다(그런데 그냥 다익스트라였다)
• 다익스트라로 슈퍼컴퓨터와 다른 컴퓨터 간 최소거리를 구함
• 경로를 저장해서 해당 경로만 출력, 이전처럼 이전노드만 저장하는 방식으로 풀면될듯

 

class Node implements Comparable<Node> {
    int value;
    int end;

    public Node(int value, int end) {
        this.value = value;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

class Line {
    int a;
    int b;
    int time;

    public Line(int a, int b, int time) {
        this.a = a;
        this.b = b;
        this.time = time;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static int[] values;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int computerCnt = Integer.parseInt(st.nextToken());
        int lineCnt = Integer.parseInt(st.nextToken());

        arr = new ArrayList[computerCnt];

        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<lineCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a= Integer.parseInt(st.nextToken())-1;
            int b= Integer.parseInt(st.nextToken())-1;
            int time= Integer.parseInt(st.nextToken());

            arr[a].add(new Node(time, b));
            arr[b].add(new Node(time, a));
        }

        dijkstra(0);
    }

    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, start));

        boolean[] visit = new boolean[arr.length];
        int[] prev = new int[arr.length];

        values = new int[arr.length];
        Arrays.fill(values, Integer.MAX_VALUE);
        values[start] = 0;
        prev[start] = start;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (!visit[curr]) {
                visit[curr] = true;
                for (Node adj: arr[curr]) {
                    if (!visit[adj.end] && values[adj.end] > values[curr] + adj.value) {
                        values[adj.end] = values[curr] + adj.value;
                        prev[adj.end] = curr;
                        pq.add(new Node(values[adj.end], adj.end));
                    }
                }
            }
        }

        HashSet<String> set = new HashSet<>();
        for (int i =1; i<values.length; i++) {
            int num = i;
            while (true) {
                int p = prev[num];
                if (num == 0) {
                    break;
                }
                set.add("" + Math.min(num+1, p+1) + " " + Math.max(num+1, p+1));
                num = p;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(set.size() + "\n");
        Iterator it = set.iterator();
        while (it.hasNext()) {
            sb.append(it.next() + "\n");
        }

        System.out.print(sb);
    }
}

 

 

뿌수기 4까지 가야할듯하다.. 아직 덜뿌쉈다