[Algorithm] Dijkstra 알고스팟 (백준), nextLine() 주의사항 - 에이젠

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

1261번: 알고스팟

공략

다익스트라 알고리즘 문제 입니다. 

정답률은 41퍼센트 정도로 어렵지 않게 풀 수 있는 문제입니다.

하지만 이전에 풀어본 다익스트라 문제와 다른 부분이 있기에 생각을 하게 만드는 문제였습니다.

그동안 노드들을 인접리스트를 사용해 쉽게 나타내었지만

이문제는 각각의 노드들이 2차원배열 요소이기 때문에 자료구조를 다르게 사용해야 합니다.

 

우선 Info class의 기존에 idx변수를 행(inxX)과 열(inxY)로 변경합니다.

dist 2차원배열 : 각 좌표까지 부서지는 벽의 최소 개수.

matrix :  입력받는 미로

N : 세로

M : 가로

dir : 상하좌우 이동 방향

입력받는 함수를 구현해줍니다.

nextLine을 사용하면  IndexOfBounds 에러가 생깁니다. 

next()는 개행문자를 무시하고 입력을 받고 nextLine은 한줄 단위로 입력을 받기 때문에 개행문자로 포함하게 됩니다.

따라서 nextInt()를 사용한 직후에 nextLine()을 사용하게 되면 남아있는 엔터값을 읽게되면서 에러 발생.

 

static void dijkstra() {
    dist = new int[N + 1][M + 1];

    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= M; j++) {
        dist[i][j] = Integer.MAX_VALUE;
      }
    }

    PriorityQueue<Info> heap = new PriorityQueue<Info>(Comparator.comparing(o -> o.distance));

    dist[1][1] = 0;
    heap.add(new Info(1, 1, 0));

    while (!heap.isEmpty()) {
      Info info = heap.poll();

      if (info.distance != dist[info.idxX][info.idxY])
        continue;

      for (int i = 0; i < 4; i++) {
        // 좌표를 벗어나면 패스
        if (info.idxX + dir[i][0] <= 0
            || info.idxX + dir[i][0] > N
            || info.idxY + dir[i][1] <= 0
            || info.idxY + dir[i][1] > M) {
          continue;
        }

        else if (matrix[info.idxX + dir[i][0]][info.idxY + dir[i][1]]
            + dist[info.idxX][info.idxY] < dist[info.idxX + dir[i][0]][info.idxY + dir[i][1]]) {

          heap.add(new Info(
              info.idxX + dir[i][0],
              info.idxY + dir[i][1],
              matrix[info.idxX + dir[i][0]][info.idxY + dir[i][1]]
                  + dist[info.idxX][info.idxY]));

          dist[info.idxX + dir[i][0]][info.idxY + dir[i][1]] = matrix[info.idxX + dir[i][0]][info.idxY + dir[i][1]]
              + dist[info.idxX][info.idxY];

        }

      }
    }

  }