Today's Algorithm(2018-11-12)

boj 14940. 쉬운 최단거리

이번 문제의 경우 풀다가 제가 선언한 변수들을 제가 헷갈려버리기 시작하면서 미궁으로 빠졌고 시간이 꽤 오래 걸렸습니다. 이후 미궁으로 빠졌던 부분에서 겨우 빠져나오고 나서야 제출할 수 있었는데요. 답은 맞았지만 참 찝찝한 느낌이 듭니다. 다음과 같은 이유들 때문입니다.

• 코드에서 비효율성, 반복이 너무 많이 보입니다. 반복되는 부분, 다른 조건에서 다 처리할 수 있는 부분이 곳곳에 보였지만 지역변수들이 너무 많아 헷갈려서 많이 줄이지 못하였습니다.
• 앞에서 말한대로 지역변수들이 너무 많이 선언되어 제가 선언한 것임에도 불구하고 무엇을 의미하는건지 많이 헷갈렸습니다.
• 시간과 메모리에서 둘 다 다른 사람들에 비해 좋지 않습니다.

이런 점에서 내일은 다른 알고리즘 문제를 풀지 못하더라도 맞은 사람의 코드를 분석하면서 위에서 제가 부족했던 부분을 어떻게 해결했는지 보면서 배우고 다시 개선하여 코드를 짜보려합니다.

 

그래도 오늘 푼 문제는 짧게 정리해볼게요. 입력과 출력을 보겠습니다.

입력과 출력을 보면 바로 알겠듯이 DFS(너비 우선 탐색)을 푸는 문제입니다. 다만 주의할 점은 출력 조건에 벽이 있으면 0, 그리고 닿지 않는 거리이면 -1로 출력한다는 점입니다. 근데 DFS로 풀다보면 벽 때문에 갈 수 없는 거리는 애초 그곳에 가지도 않기 때문에 출력값을 -1로 바꿀 수도 없습니다. 따라서 애초에 초기화할 때부터 -1로 해두는 것이 좋습니다. 이후에 바꾸는 것이죠. 그 외엔 평소 DFS 풀듯이 풀면 되는데 수가 많다보니 더더욱 많이 헷갈리더라구요.

 

package b14940;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
b
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.parseInt(s)).toArray();
        int rowNum = input[0];
        int colNum = input[1];
        int[][] d = new int[rowNum][colNum];
        int[][] check = new int[rowNum][colNum];
        int[][] answer = new int[rowNum][colNum];
        int startR = 0, startC = 0;
        Queue<Point> q = new LinkedList<>();
        // 동, 서, 남, 북 움직이도록
        int[] directRow = {0, 0, -1, 1};   
        int[] directCol = {1, -1, 0, 0}; 

        // 입력
        for (int i = 0; i < rowNum; i++) {
            int[] rowArr = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.parseInt(s)).toArray();
            for (int j = 0; j < colNum; j++) {
                d[i][j] = rowArr[j];
                answer[i][j] = -1;   // -1로 초기화
                if(rowArr[j] == 2) {   // 시작점
                    startR = i; startC = j;
                    check[startR][startC] = 1;
                    answer[startR][startC] = 0;
                }
                if(rowArr[j] == 0) {
                    answer[i][j] = 0;
                }
            }
        }

        // 맨 처음 큐에 넣기
        for (int i = 0; i < directCol.length; i++) {
            int tempRow = startR + directRow[i];
            int tempCol = startC + directCol[i];
            if(tempCol > -1 && tempCol < colNum && tempRow > -1 && tempRow < rowNum && d[tempRow][tempCol] != 0) {
                Point point = new Point(tempRow, tempCol);
                q.offer(point);
                point.distance = 1;
                check[tempRow][tempCol] = 1;
                answer[tempRow][tempCol] = 1;
            }
        }

		// DFS
        while(!q.isEmpty()) {
            Point point = q.poll();
            for (int i = 0; i < directRow.length; i++) {
                int tempRow = point.row + directRow[i];
                int tempCol = point.col + directCol[i];
                if(tempCol > -1 && tempCol < colNum && tempRow > -1 && tempRow < rowNum) {
                    if(d[tempRow][tempCol] == 1 && check[tempRow][tempCol] == 0) {
                        Point nextPoint = new Point(tempRow, tempCol);
                        nextPoint.distance = point.distance + 1;
                        q.offer(nextPoint);
                        check[tempRow][tempCol] = 1;
                        answer[tempRow][tempCol] = point.distance + 1;
                    } else {
                        check[tempRow][tempCol] = 1;
                    }
                }
            }
        }

        for (int[] ints : answer) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}

class Point {
    int row;
    int col;
    int distance;

    public Point(int x, int y) {
        this.row = x;
        this.col = y;
    }
}

맨 처음 큐에 넣는 수랑 DFS 안의 코드가 겹치는 부분이 많습니다. 이 부분을 중점적으로 개선하고 싶습니다. 또 Point보다는 C++처럼 Pair inner Class로 만들어서 해결하시는 분도 계시더라구요. 내일 하면서 어떤 것이 더 좋은지 판단해봐야겠습니다!