Path Finder #1: can you reach the exit?, CodeWars Kata 자바 솔루션

 

Path Finder #1: can you reach the exit?, CodeWars Kata

Path Finder #1: can you reach the exit?

Task

You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return true if you can reach position [N-1, N-1] or false otherwise.

• Empty positions are marked ..
• Walls are marked W.
• Start and exit positions are empty in all test cases.

Path Finder Series:

• #1: can you reach the exit?
• #2: shortest path
• #3: the Alpinist
• #4: where are you?
• #5: there's someone here

 

문제 해석

개행문자로 구분된 N*N의 행렬이 입력값으로 제공됩니다. 행렬은 .과 W로 이루어져 있으며 .는 이동할 수 있는 칸을 의미하고 W는 벽, 즉 이동할 수 없는 칸을 의미합니다. 우리는 [0, 0] 위치에서 시작해서 [N-1, N-1]에 갈 수 있으면 true를 리턴하고 갈 수 없다면 false를 리턴해야 합니다.

입력값

• String maze: 개행문자로 구분된 .과 W로 이루어진 N*N의 행렬

출력값

• boolean result: [N-1, N-1]에 도달 가능 여부

 

My Solution

저는 입력 문자열을 2차원 배열로 변환하지 않고 갯수만 센 후 개행문자를 제거하여 1차원 배열로 다뤘습니다. 각각의 칸을 그래프의 정점으로 보고 인접한 칸으로 이동 가능하다면 간선이 존재하는 것으로 간주했습니다.

먼저 LinkedList<Integer>[] link 를 생성해 간선을 모두 입력했습니다. 하나의 칸을 기준으로 동서남북 칸으로 이동 가능한 지 체크 한 후 이동 가능한 칸들을 담아줍니다.

그 다음은 스택을 이용했습니다. Stack<Integer> stack을 생성하고 시작점인 link[0]에서 갈 수 있는 칸들을 모두 스택에 넣어줍니다. 그 다음은 스택을 pop()하여 해당 칸에서 갈 수 있는 칸들을 스택에 쌓습니다. 이렇게 이동 가능한 칸들을 서치하면서 출구 칸([N-1, N-1] 저의 코드에서는 [N * N - 1]) 에 도달하면 true를 리턴해 줍니다. 한 번 이동했던 칸은 다시 갈 필요가 없으므로 boolean[] visited을 활용했습니다.

모든 칸을 탐색했음에도 도달하지 못하면 false를 리턴합니다.

솔루션 코드

테스트 코드

import java.util.LinkedList;
import java.util.Stack;

public class Finder {
    
    static boolean pathFinder(String maze) {
        int N = maze.indexOf("\n");
        maze = maze.replaceAll("\n", "");
      
        if (maze.length() == 1)
            return true;

        LinkedList<Integer>[] link = new LinkedList[N * N];
        for (int i = 0; i < N * N; i++) {
            link[i] = new LinkedList<Integer>();
            if (maze.codePointAt(i) == 'W')
                continue;

            if (i - N >= 0 && maze.codePointAt(i - N) != 'W')
                link[i].add(i - N);

            if (i / N == (i - 1) / N && i - 1 >= 0 && maze.codePointAt(i - 1) != 'W')
                link[i].add(i - 1);

            if (i / N == (i + 1) / N && maze.codePointAt(i + 1) != 'W')
                link[i].add(i + 1);

            if (i + N < N * N && maze.codePointAt(i + N) != 'W')
                link[i].add(i + N);
        }

        Stack<Integer> stack = new Stack<Integer>();
        boolean[] visited = new boolean[N * N];
        visited[0] = true;
        while (!link[0].isEmpty()) {
            stack.push(link[0].poll());
        }

        while (!stack.isEmpty()) {
            int next = stack.pop();

            if (!visited[next]) {
                visited[next] = true;
                while (!link[next].isEmpty()) {
                    stack.push(link[next].poll());
                    if (stack.peek() == N * N - 1)
                        return true;
                }
            }
        }

        return false;
    }
}

 

Best Practice

BP에서는 재귀함수를 사용했습니다. inner클래스를static으로 생성해서 사용한 것이 첫번째로 눈에 띕니다. 이 솔루션에서는 입력값 maze를 2차원 배열로 변환하여 탐색했습니다.

재귀함수를 살펴보면 먼저 종료 조건을 지정합니다. 출구를 찾으면 종료이고요. 이동할 수 있는 칸이 없다면 종료합니다. findExit(n[0],g) | findExit(n[1],g) | findExit(n[2],g) | findExit(n[3],g)을 통해서 동서남북을 계속해서 탐색합니다.

public class Finder {
  
  private static class Pos {
    final int x, y;
    Pos(int x, int y) { this.x = x; this.y = y; } 
    Pos[] neighbours() { return new Pos[]{ new Pos(x-1,y), new Pos(x+1,y), new Pos(x,y-1), new Pos(x,y+1) }; }
    boolean onPath(char[][]g) { return x >= 0 && x < g[0].length && y >= 0 && y < g.length && g[y][x] == '.'; }    
  }

  static boolean pathFinder(String maze) {
    final String rows[] = maze.split("\n");
    final char[][] grid = new char[rows.length][];
    for (int i = 0; i < rows.length; i++) grid[i] = rows[i].toCharArray();
    return findExit(new Pos(0,0), grid);
  }
  
  private static boolean findExit(Pos p, char[][]g) {        
    if (p.x == g.length-1 && p.x == p.y) return true; // We made it to the exit!    
    if (!p.onPath(g)) return false;
    g[p.y][p.x] = 'B';  // drop a breadcrumb
    final Pos[] n = p.neighbours();
    return findExit(n[0],g) | findExit(n[1],g) | findExit(n[2],g) | findExit(n[3],g);
  }

}