레이저 통신 - 자바

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

Stack이나 Queue를 사용할 때, 인접리스트를 통해서 구현하는 방법이 시간 복잡도 면에서 더 효율적이다. 단순히, stack을 사용하니 당연히 시간복잡도에서 걸려, 인접리스트를 통해 구현하였다.

import java.io.IOException;
import java.util.Queue;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.LinkedList;

public class Main {

    private static int H;
    private static int W;
    private static char[][] map;
    private static int[][] visited;
    private static List<Node> nodes = new ArrayList<>();
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};


    public static void main(String[] args) throws IOException {

        Scanner scanner = new Scanner(System.in);
        W =scanner.nextInt();
        H = scanner.nextInt();
        map = new char[H][W];

        for (int i = 0; i < H; i++) {
            String s = scanner.next();
            for (int j = 0; j < W; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'C') {
                    nodes.add(new Node(-1, i,j,0));
                }
            }
        }

        System.out.println(findRouteByDfs());
    }

    public static int findRouteByDfs() {
        Queue<Node> queue = new LinkedList<>();
        Node startNode = nodes.get(0);
        Node endNode = nodes.get(1);
        queue.add(startNode);
        visited = new int[H][W];
        visited[startNode.x][startNode.y] = 1;
        int returnMirrorCnt = 111110;

        while (queue.size() > 0) {
            Node currentNode = queue.poll();

            if (currentNode.x == endNode.x && currentNode.y == endNode.y) {
                if (returnMirrorCnt > currentNode.mirror) {
                    returnMirrorCnt = currentNode.mirror;
                }
            }
            for (int i = 0; i < 4; i++) {
                int nextX = dx[i] + currentNode.x;
                int nextY = dy[i] + currentNode.y;
                if (nextX < H && nextY < W && nextX >= 0 && nextY >= 0) {
                    if (map[nextX][nextY] != '*') {
                        if (visited[nextX][nextY] == 0) {
                            visited[nextX][nextY] = currentNode.mirror;
                            if (currentNode.direction != i  && currentNode.direction != -1) {
                                queue.add(new Node(i, nextX, nextY, currentNode.mirror + 1));
                            } else {
                                queue.add(new Node(i, nextX, nextY, currentNode.mirror));
                            }

                        } else if (visited[nextX][nextY] >= currentNode.mirror) {
                            visited[nextX][nextY] = currentNode.mirror;
                            if (currentNode.direction != i && currentNode.direction != -1) {
                                queue.add(new Node(i, nextX, nextY, currentNode.mirror + 1));
                            } else {
                                queue.add(new Node(i, nextX, nextY, currentNode.mirror));
                            }


                        }

                    }
                }
            }
        }
        return returnMirrorCnt;
    }
}
   class Node {
        public int direction;
        public int x;
        public int y;
        public int mirror;

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