[Algorithm] 탐색문제 재귀로 구현해보기

왜 하는가?

매번 재귀 문제를 풀때 재귀로 구한 답을 전역변수로 처리 할 것인지

아니면 리턴된 값들을 더해서 최종답을 구할 건지 고민이 되기 때문이다.

그래서 두방법다 정리해봅니다.

 

 

문제

• 각각의 사막기지 위치에서 가장 가까운 우물을 찾으려고 한다.
• 기지는 1 로 되어 있고 우물은 0 으로 표기한다.
• 기지위치에 가장 가까운 우물의 거리를 표기한다.

예제

Case1

{1, 0, 0}

{0, 1, 1}

{0, 1, 1}

 

예제 설명

0,0 에서 가장 가까운 거리는 1 이다 왼쪽이 될수도 있고

아래 가 될수 있다.

 

2,2 위치 에서는 가장 가까운 우물은 0,2 또는 2,0 이된다.

 

그렇게 위치를 기록하면 다음과 같다.

Case1 의 답

|1|0|0|
|0|1|1|
|0|1|2|

 

Case2

{0,1,1,0}

{1,1,1,0}

{1,1,1,1}

{1,1,1,1}

 

Case2 의 답

|0|1|1|0|
|1|2|1|0|
|2|3|2|1|
|3|4|3|2|

 

 

구현1

찾은 답은 전역변수에 저장하는 방식입니다.

package com.company;

public class Solution1 {

    // 왼쪽 오른쪽 위 아래 이동방향
    int _dirX[] = {-1,1,0,0};
    int _dirY[] = {0,0,1,-1};

    // 맵의 최대 크기
    int _mapX = 0;
    int _mapY = 0;
    
    // 최소 값을 찾기 위한 전역변수
    int _minDist = 987654321;

    // 방문했는지 체크
    // 체크를 안하면 계속 똑같은 곳을 방문할수 있다.
    // 스택 오버 플로우 발생
    boolean [][]visit;

    // 진행 사항을 출력
    boolean printFlag = false;

    // 바운더리 체크
    public boolean checkBoundary(int x, int y) {
        if(x < 0 || x >= _mapX || y < 0 || y >= _mapY) {
            return false;
        } else {
            return true;
        }
    }

    // DFS
    public void solve(int x, int y, int [][]map, int dist) {
        if(printFlag) {
            System.out.println(x+","+y+","+dist);
            for(int i = 0; i < visit.length; i++) {
                for(int j = 0; j < visit.length; j++) {
                    if(visit[i][j]) {
                        System.out.print(1);
                    } else {
                        System.out.print(0);
                    }

                }
                System.out.println();
            }
        }

        // 우물 위치를 찾으면
        // 이전에 찾은 값과 비교해서 거리가 더 짧은지 체크한다.
        if(map[x][y] == 0) {
            if(_minDist > dist) {
                _minDist = dist;
            }
            return;
        }

        // 지금까지 구한 거리보다 더 크면 탐색할 필요가 없다.
        if(_minDist < dist) {
            return;
        }

        // 현재 위치를 방문 했다고 표기
        visit[x][y] = true;
        for(int i = 0; i < 4; i ++) {
            int dx = x+_dirX[i];
            int dy = y+_dirY[i];
            if (checkBoundary(dx, dy) && !visit[dx][dy]) {
                solve(dx,dy,map,dist+1);
            }
        }
        
        // 다음 값을 찾기 위해 방문 했던 것을 다시 false 로 한다.
        visit[x][y] = false;

        return;
    }

    public void solution(int [][]map, int [][]answer){
        _mapX = map.length;
        _mapY = map[0].length;
        for(int i = 0; i < map.length; i++){
            for(int j = 0; j < map[i].length; j++){
                if(map[i][j] == 1) {
                    if(i == 0 && j == 1){
                        printFlag = true;
                    } else {
                        printFlag=false;
                    }
                    _minDist = 987654321;
                    visit = new boolean[map.length][map[0].length];
                    solve(i,j,map,0);
                    System.out.println("x: " + i + " y: " + j + " minDist: " + _minDist);
                    answer[i][j] = _minDist;
                }
            }
        }
    }

    public static void main(String[] args) {
        // write your code here
        Solution1 solution1 = new Solution1();

        int[][] map1 = {{1, 0, 0}, {0, 1, 1}, {0, 1, 1}};
        int[][] answer1 = new int[3][3];
        solution1.solution(map1, answer1);
        System.out.println("CASE 1");
        for (int i = 0; i < answer1.length; i++) {
            for (int j = 0; j < answer1[0].length; j++) {
                System.out.print("|" + answer1[i][j]);
            }
            System.out.print("|");
            System.out.println("");
        }


        int[][] map2 = {{0,1,1,0}, {1,1,1,0}, {1, 1, 1, 1}, {1,1,1,1}};
        int[][] answer2 = new int[map2.length][map2.length];
        solution1.solution(map2, answer2);
        System.out.println("CASE 2");
        for (int i = 0; i < answer2.length; i++) {
            for (int j = 0; j < answer2[0].length; j++) {
                System.out.print("|" + answer2[i][j]);
            }
            System.out.print("|");
            System.out.println("");
        }
    }
}

 

구현2

전역변수를 사용하지 않고 리턴 값으로 최소값을 구하는 로직입니다.

package com.company;

public class Solution2 {

    int _dirX[] = {-1,1,0,0};
    int _dirY[] = {0,0,1,-1};

    int _mapX = 0;
    int _mapY = 0;

    boolean [][]visit;

    boolean printFlag = false;

    public boolean checkBoundary(int x, int y) {
        if(x < 0 || x >= _mapX || y < 0 || y >= _mapY) {
            return false;
        } else {
            return true;
        }
    }


    public int solve(int x, int y, int [][]map) {
        if(printFlag) {
            System.out.println(x+","+y);
            for(int i = 0; i < visit.length; i++) {
                for(int j = 0; j < visit.length; j++) {
                    if(visit[i][j]) {
                        System.out.print(1);
                    } else {
                        System.out.print(0);
                    }

                }
                System.out.println();
            }
        }

        if(map[x][y] == 0) {
            return 1;
        }


       
        visit[x][y] = true;
       
       // 지금까지 방문 했던거리중 짧은 거리를 찾기 위한 값
       int minDistance = 987654321;
        for(int i = 0; i < 4; i ++) {
            int dx = x+_dirX[i];
            int dy = y+_dirY[i];
            if (checkBoundary(dx, dy) && !visit[dx][dy]) {
                // 방문했던 값들중 최소 값을 찾는다.
                int tmpDistance = solve(dx,dy,map);
                if(minDistance > tmpDistance) {
                    minDistance = tmpDistance;
                }
            }
        }
        visit[x][y] = false;

        // 최소값에 + 1을 해준다: 지금까지 찾은값 + 현재 방문한 스텝
        return minDistance+1;
    }

    public void solution(int [][]map, int [][]answer){
        _mapX = map.length;
        _mapY = map[0].length;
        for(int i = 0; i < map.length; i++){
            for(int j = 0; j < map[i].length; j++){
                if(map[i][j] == 1) {
                    if(i == 0 && j == 1){
                        printFlag = true;
                    } else {
                        printFlag=false;
                    }
                    visit = new boolean[map.length][map[0].length];
                    System.out.println("x: " + i + " y: " + j + " minDist: ");
                    answer[i][j] = solve(i,j,map);
                }
            }
        }
    }

    public static void main(String[] args) {
        // write your code here
        Solution1 solution1 = new Solution1();

        int[][] map1 = {{1, 0, 0}, {0, 1, 1}, {0, 1, 1}};
        int[][] answer1 = new int[3][3];
        solution1.solution(map1, answer1);
        System.out.println("CASE 1");
        for (int i = 0; i < answer1.length; i++) {
            for (int j = 0; j < answer1[0].length; j++) {
                System.out.print("|" + answer1[i][j]);
            }
            System.out.print("|");
            System.out.println("");
        }


        int[][] map2 = {{0,1,1,0}, {1,1,1,0}, {1, 1, 1, 1}, {1,1,1,1}};
        int[][] answer2 = new int[map2.length][map2.length];
        solution1.solution(map2, answer2);
        System.out.println("CASE 2");
        for (int i = 0; i < answer2.length; i++) {
            for (int j = 0; j < answer2[0].length; j++) {
                System.out.print("|" + answer2[i][j]);
            }
            System.out.print("|");
            System.out.println("");
        }
    }
}

 

 

 

 

결론

이해하기 쉬운 방식으로 먼저 이해한다.

둘중에 어느 방법을 택할 지는 상황에 따라 고려를 해본다.

 

전역변수는: 매번 탐색을 시작 할때마다 전역변수 값을 초기화 해줘야한다.

리턴방법: 전역변수를 신경쓰지 않아도 되지만, 정확하게 계산 방법을 고려해야된다.