Today's Algorithm(2018-11-13)

boj 14940. 쉬운 최단거리 리팩토링

어제 이 문제를 풀면서 제대로 풀지 못했다는 생각에 조금 아쉬웠는데요. 오늘 저보다 잘하시는 분들의 코드를 보면서 어떻게 좀 더 간단하면서도 명확하게 풀 수 있는지 배우게 되었습니다. 그분의 코드를 보고 느낀점을 정리해볼께요.

 

• 변수 이름 짓기

  • DFS 풀다보면 배열이 필요한데요. 저의 경우 익숙하지 않다보니 배열명을 막 지었고 그렇다보니 뒤에서 쓰면서 많이 헷갈렸던 것 같아요. 그래서 아래에 몇 개 유용하다고 생각하는 이름을 적겠습니다.
  • visited(방문 체크), map(지도 값들)

• 입력값 배열에 넣을 때 StringTokenizer의 사용

  • 이건 개인 스타일의 차이일 수도 있는데 StringTokenizer를 사용하면 띄워쓰기에 따라 알아서 구분해주기 때문에 좀 더 깔끔하게 사용할 수 있는 것 같습니다.
  • 불러올 때는 nextToken() 메서드를 사용하면 됩니다

• 큐의 값을 비교할 때 조건을 만족하는 값을 찾지 말고, 조건을 만족하지 않는 값을 떨쳐낼 것!

  • 이 부분이 가장 유용하다고 생각했던 부분입니다. 제가 만족하려는 값들을 찾다보니 계속 if문이 많아지고 그 변수들 사이에서 많이 헷갈렸거든요.. 모두를 만족하려는 값을 찾는 것보다 만족하지 않는 것 모두 밀쳐내는게 더 실수 방지에 좋은 것 같아요!!
  • 그래서 이 문제의 경우 map범위 벗어났을 때, 방문한 곳일때, 막힌 곳일때 이렇게 세 가지 체크해주고 만약 위 세 가지 중 하나이면 continue를 통해 아무런 처리하지 않는 것입니다.
  • 그리고 이 세가지를 모두 통과했으면 이후에 그 값들을 가지고 (상, 하, 좌, 우) 돌아가면서 큐에 넣고, 여러 값 처리하는 것이죠.

• 출력할 때는 System.out.print 대신 StringBuffer 이용하기

  • StringBuffer 로 append() 로 다 모은 다음에 한번에 출력하더라구요!

• Pair inner class 만들기

  • 저도 이전에 Point inner class만들었는데요. 이건 사실 뭘로 만들든 크게 중요하지 않은 것 같아요.
  • 그런데 중요한건 이 값이 기본적으로 좌표값을 가지고 있으면서, 거리값도 가지고 있어야 한다는 점입니다. 그렇게 해야 다음 값에 기존 거리값을 이용하여 넣어줄 수 있거든요.

 

위 내용을 조합하면 이런 코드가 되는 것입니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
        int[][] map = new int[r][c];
        int[][] ans = new int[r][c];
        int startR = 0;
        int startC = 0;
        for (int i = 0; i < r; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                ans[i][j] = -1;
                if (map[i][j] == 2) {
                    startR = i;
                    startC = j;
                }
                if (map[i][j] == 0) {
                    ans[i][j] = 0;
                }
            }
        }

        int[] dr = {0, 0, -1, 1};
        int[] dc = {1, -1, 0, 0};
        boolean[][] visited = new boolean[r][c];
        ans[startR][startC] = 0;
        visited[startR][startC] = true;

        Queue<Pair> queue = new LinkedList<>();
        for (int i = 0; i < dr.length; i++) {
            queue.add(new Pair(startR + dr[i], startC + dc[i], 1));
        }

        while (!queue.isEmpty()) {
            Pair t = queue.poll();
            if(t.c < 0 || t.c >= c || t.r < 0 || t.r >= r) continue;
            if(visited[t.r][t.c]) continue;
            if(map[t.r][t.c] == 0) continue;
            visited[t.r][t.c] = true;
            ans[t.r][t.c] = t.w;
            for (int i = 0; i < dr.length; i++) {
                queue.add(new Pair(t.r + dr[i], t.c + dc[i], t.w + 1));
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int[] an : ans) {
            for (int i : an) {
                sb.append(i + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

class Pair {
    int r, c, w;

    public Pair(int r, int c, int w) {
        this.r = r;
        this.c = c;
        this.w = w;
    }
}