TopCoder 문제로 연습해보는 알고리즘: 초급 (2) 전체 탐색 (2/2)

TopCoder 알고리즘 트레이닝
https://book.naver.com/bookdb/book_detail.nhn?bid=7333164

TopCoder 알고리즘 트레이닝

5장 전체 탐색의 6~9 챕터까지 정리해본 내용입니다

 

---

 

그래프 탐색 알고리즘

1. 깊이 우선 탐색: DFS, Depth First Search

탐색을 위해 스택을 이용함 → 재귀 Recursion
메모리에 추가되는 노드를 LIFO로 처리함:
호출하는 순간 그 다음 정점으로 처리가 이동하여 그 정점에서 처리가 완료된 후 호출했던 자리로 돌아온다

1) 재귀 함수 예시: fibonacci

int fib(int n){
    if(n<=1) return 1;
    return fib(n-1) + fib(n-2);
}

2) 깊이 우선 탐색법의 구현 예시

//처리했던 데이터를 기억시킬 자료구조
...

int dfs(Object data){
    if(말단 노드임을 확인할 수 있는 data 조건) return 말단 노드의 처리 값;
    if(이전에 처리했던 데이터라면) return 처리한 데이터에 대해 리턴해 줄 값;
    //중간 노드의 처리과정
    int ret=0;
    for(int i=0; i<다음으로 방문할 하위 노드의 개수; i++){
        //누적합을 구한다거나..
        ret += dfs(i번째 후속 노드에서 처리해 올 data);
        //후속 노드에서 처리한 값을 리턴받아서 최댓값, 최솟값을 비교한다거나 .. 등등
        ret = Math.max(dfs(i번째 후속 노드로 가는 data), ret);
    }
    return ret;
}

3) DFS를 사용하는 대표적인 예시

• 모든 경로를 탐색해 본 후에 결과를 총 정리해야 하는 경우
• 문자열 등을 탐색할 때, '사전 순서'등 순서대로 앞부터 검색해서 찾는 것이 빠른 경우

 

 

2. 너비 우선 탐색Breadth First Search

탐색을 위해 큐, 배열, 리스트 등을 사용함
메모리에 추가되는 노드를 FIFO로 처리함

1) 너비 우선 탐색의 구현 예시

Queue<T> q = new LinkedList<T>();
q.add(초기 상태);

//처리했던 데이터를 기억시킬 자료구조
...

while(!q.isEmpty){//큐에 처리할 노드가 없어질 때까지
    //큐에서 가장 오래된 노드를 하나 pop해온다
    T now = q.poll(); 
    //해당 노드를 처리함 ...

    //처리해야 하는 다음 노드가 있다면 큐에 추가한다
    for(int i=0; i<다음으로 방문할 하위 노드의 개수; i++){
        T next = i번째 다음 노드;
        if(i번째 다음 노드(next)의 데이터를 처리한 적이 없다면) //중복 처리를 방지하기 위해
                q.add(next);
    }
}

2) BFS를 사용하는 대표적인 예시

• 시작 지점에서 가장 가까운 지점(루트 노드에서 가까운 순서로 하위 노드에 접근해야 할 경우)
• 트리가 굉장히 넓고 깊어서, 깊이 우선 탐색을 사용해서 찾으려면 대량의 스택을 사용해야 하는 경우

 

3. Bit 전체 탐색

포화 이진 트리의 경우에는 각 노드에 2진수 값을 대응할 수 있다

• 왼쪽에서부터 오른쪽으로 말단 노드를 0~7로 번호를 붙인다면
• 0번은 000₍₂₎, 1번은 001₍₂₎, ... , 6번은 110₍₂₎, 7번은 111₍₂₎

2진수 값의 각 자리 ☐☐☐에 대응되는 0과 1은 서브트리의 왼쪽/오른쪽에 대응된다

• 000₍₂₎은 루트 노드에서 왼쪽 → 왼쪽 → 왼쪽에 있는 노드
• 111₍₂₎은 루트 노드에서 오른쪽 → 오른쪽 → 오른쪽에 있는 노드

1) 장점

n개 요소에 대한 모든 O/X의 경우의 수를 따져볼 때 편리하다

• 왼쪽(0)과 오른쪽(1)을 '사용한다', '사용하지 않는다'로 분기하는 트리에 대응시킬 수 있다
  • 2ⁿ개의 말단 노드만 탐색하면 됨
  • 0~2ⁿ-1까지 말단 노드에 대한 반복문을 돌리면 된다

2) 단점: DFS를 쓰는게 더 나은 경우

• DFS처럼 중복 처리를 방지할 수가 없다
• 자식 노드의 처리 결과를 기반으로 부모 노드의 처리 결과를 도출하는 경우라면
  DFS를 쓰는 것이 처리에 있어 효율적이다

 

---

 

문제 풀이

1. CrazyBot

Problem

평면 위의 로봇은
1) 동/서/남/북 중 한 방향을 랜덤으로 선택하여, 
2) 한 칸씩 총 n번을 움직인다.
3) 통과했던 지점을 또 지나면 실패.

각 방향을 선택할 확률은 east, west, south, north%
로봇이 성공적으로 보행할 확률을 double로 리턴

int n 로봇이 움직이는 횟수 (1~14)
int east, west, south, north (0~100, 총합은 100)
returns double 성공할 확률 

Example Data

0)
n=1
east=25
west=25
south=25
north=25
returns: 1.0

1)
n=2
east=25
west=25
south=25
north=25
returns:0.75

2)
n=7
east=50
west=0
south=0
north=50
returns: 1.0

3)
n=14
east=50
west=50
south=0
north=0
returns: 2/(2¹⁴)확률

Solve

로봇의 다음 움직임에 대한 확률 값을 노드로 가지는 트리를 그려볼 수 있고
가능한 경우 중 성공하는 경우의 값만 총합을 구하면 된다: 깊이 우선 탐색

로봇이 가게 되는 지점을 좌표 평면으로 나타낼 수 있고,
다음 지점을 평면상 좌표로 나타내어 생각한다
- east(1,0)
- west(-1,0)
- south(0,-1)
- north(0,1)

로봇이 한번 방문했던 지점을 다시 방문하는 경우 그 다음 움직임에 대해서는 고려하지 X (보행실패)
→ 해당 노드의 하위 노드는 탐색할 필요가 없다 
→ 중복된 방문인 경우 return값 지정해줘서 더 깊이 탐색하지 않도록 하자

public class CrazyBot {

    // 로봇이 방문한 곳을 기억하기 위한 그리드
    // 한번에 직선으로 가장 멀리 갈 수 있는 지점은 +14까지, 적당히 30*30의 그리드를 준비함
    boolean[][] grid = new boolean[30][30];

    // (cx[i],cy[i])로 동서남북의 이동 좌표
    int[] cx = { 1, -1, 0, 0 };
    int[] cy = { 0, 0, -1, 1 };

    // 다른 메소드에서도 접근 가능하도록 전역 변수
    double[] probs = new double[4];

    public double getProb(int n, int east, int west, int south, int north) {

        probs[0] = east/100.0;
        probs[1] = west/100.0;
        probs[2] = south/100.0;
        probs[3] = north/100.0;

        //만약 필요하다면 grid를 초기화- java는 선언시 기본값으로 초기화되어 안 해도 됨
        /*
        for(int i=0; i<30; i++){
            for(int j=0; j<30; j++){
                grid[i][j] = false;
            }
        }*/

        return dfs(15,15,n);
    }

    public double dfs(int x, int y, int n) {

        //방문했던 지점을 방문하게 되는 경로인 경우, 경로 무효화
        if(grid[x][y]) return 0;
        //움직이는 횟수를 다 사용한 경우 (말단 노드)
        if(n==0) return 1.0;

        //방문하게 된 지점을 표시함
        grid[x][y] = true;

        double ret = 0.0;
        for(int i=0; i<4; i++){ 
            //동서남북 순서로 각각 다음 좌표에 대한 확률을 처리하여 리턴받는다
            ret += dfs(x+cx[i], y+cy[i], n-1) * probs[i];
        }

        //처리를 완료한 지점에 대해서는 방문 표시를 초기화
        grid[x][y] = false;

        return ret;
    }

}

 

2. MazeMaker

Problem

Mike가 만드는 미로의 크기는 i*j다. 
'.'으로 표시된 칸은 지나갈 수 있고, 'X'로 표시된 칸은 지나갈 수 없다.
Jim은 메이즈의 [startRow][startCol]에서 미로 탈출을 시작한다.
Jim은 한번에 움직일 때 기존 위치 [r][c]에서 [r + moveRow[i]][c + moveCol[i]]로 이동한다

Mike는 Jim이 미로를 탈출하기 어렵게 만들 것이다.
1) Jim이 이동할 수 없는 칸이 있다면 그 칸에 출구를 둘 것이고
2) 모든 칸에 이동이 가능하다면 도달하는데 최대한 많은 이동 횟수가 필요한 칸에 출구를 둘 것이다

String[N][M] maze
int startRow (0~N)
int startCol (0~M)
maze[startRow][startCol] = '.'

int[] moveRow, int[] moveCol
(-50~50 중 최대 50개까지 같은 개수를 가지는 배열)

returns: int (1의 경우에는 -1, 2의 경우에는 해당 칸의 이동 횟수)

Example Data

0)
maze = { "...",
                 "...",
                 "..." }
startRow = 0
startCol = 1
moveRow = {1, 0, -1, 0}
moveCol = {0, 1, 0, -1}
returns: 3

1)
maze = { "...",
                 "...",
                 "..." }
startRow = 0
startCol = 1
moveRow = {1, 0, -1, 0, 1, 1, -1, -1}
moveCol = {0, 1, 0, -1, 1, -1, 1, -1}
returns: 2

2)
maze = { "X.X",
                 "...",
                 "XXX",
                 "X.X" }
startRow = 0
startCol = 1
moveRow = {1, 0, -1, 0}
moveCol = {0, 1, 0, -1}
returns: -1

3)
maze = { ".......",
                 "X.X.X..",
                 "XXX...X",
                 "....X..",
                 "X....X.",
                 "......." }
startRow = 5
startCol = 0
moveRow = {1, 0, -1, 0, -2, 1}
moveCol = {0, -1, 0, 1, 3, 0}
returns: 7

Solve

바로 다음으로 갈 수 있는 칸을 하나씩 처리해나가는 것이 필요하다: 너비 우선 탐색 BFS

Queue로 다음 갈 지점을 기억하고, 
다음으로 갈 수 없는 지점이 없을 때까지 계속해서 탐색한다. 

방문 여부 및 누적된 이동 횟수를 기억하기 위한 2차원 배열이 필요하다
- 방문하지 않음 혹은 방문할 수 없음 
- 누적 이동 횟수 : 시작점 = 0, 다음 방문 지점은 이전 지점 +1
→ 0값을 따로 표시하기 위해 방문하지 않은 지점을 -1로 초기화하자 

다음으로 갈 칸이 다음과 같을 경우 경로 탐색을 중지함!
- 'X' (갈 수 없는 칸) 이거나
- 미로 밖으로 벗어나는 좌표거나
- 이미 방문한 경우 

최종 리턴값은
- 도달하지 못하는 칸이 있다면 -1
- 전체 다 도달할 수 있었다면 그 중 이동횟수가 제일 큰 수

Row와 Col이 여러개 나오므로 순서를 헷갈리지 않도록 주의하자.....

import java.util.*;

public class MazeMaker {

    private static int longestPath(String[] maze, int startRow, int startCol, 
                                   int[] moveRow, int[] moveCol) {
                //리턴값을 위한 변수
        int ret=0;

        //방문 여부 및 누적 이동량 기록을 위한 dp[][]
        int mazeRow=maze.length; //row=행의 갯수
        int mazeCol=maze[0].length(); //col=열의 갯수 *헷갈리기 쉽다*
        int[][] dp = new int[mazeRow][mazeCol];

        //모든 값을 -1로 초기화
        for(int i=0; i<mazeRow; i++)
            for(int j=0; j<mazeCol; j++)
                dp[i][j] = -1;

        //시작 지점 표시
        dp[startRow][startCol]=0;

        //BFS를 위한 Queue
        Queue<Integer> queRow = new LinkedList<Integer>();
        Queue<Integer> queCol = new LinkedList<Integer>();

        //시작 지점 다음 노드 처리를 위해 첫 지점 add
        queRow.add(startRow);
        queCol.add(startCol);

        //BFS 시작
        while(!queRow.isEmpty()){//더이상 이동 가능한 다음 칸이 없을 때까지 반복
                        //탐색의 기준이 되는 현재 좌표를 que에서 꺼내기
            int nowRow = queRow.poll();
            int nowCol = queCol.poll();

            //기준 좌표로부터 이동 가능한 다음 칸들을 모두 탐색
            for(int i=0; i<moveRow.length; i++){
                //i번째 이동 가능한 칸의 좌표
                int nextRow = nowRow + moveRow[i];
                int nextCol = nowCol + moveCol[i];

                //이동할 수 있는 칸인지 조건 검사
                if(nextRow>=0 && nextRow<mazeRow 
                   && nextCol>=0 && nextCol<mazeCol 
                   //행과 열의 좌표가 maze 전체 범위에서 벗어나지 않으면서
                    && maze[nextRow].charAt(nextCol)=='.' //접근 가능한 칸이고
                    && dp[nextRow][nextCol]== -1 ){ //아직 지나가지 않은 칸일때
                    
                        //이동하게 되는 칸에 누적 이동 횟수를 기록한다 (기존 이동횟수 +1)
                        dp[nextRow][nextCol] = dp[nowRow][nowCol] + 1; 

                        //다다음 이동의 처리를 위해 이 좌표를 큐에 추가한다
                        queRow.add(nextRow);
                        queCol.add(nextCol);
                    }
            }

        }

        //처리가 다 끝난 후 return할 값을 검사
        for(int i=0; i<mazeRow; i++){
            for(int j=0; j<mazeCol; j++){
                //접근할 수 있는 칸이었는데 도달하지 못한 경우 -1를 리턴
                if(maze[i].charAt(j)=='.' && dp[i][j]==-1)
                    return -1;
                //-1의 값이 아닌 경우 최대 누적 이동 수를 구한다
                else 
                    ret = Math.max(ret, dp[i][j]);
            }
        }

        return ret;
    }
}

 

3. NumberMagicEasy

Problem

Taro는 Hanako가 1~16 중 고른 수를 맞춰보려고 한다.
숫자 카드를 4번 보여주면서 Hanako의 대답을 듣고 정답 숫자를 맞출 것이다.
카드 1에는 {1, 2, 3, 4, 5,  6,  7,  8}
카드 2에는 {1, 2, 3, 4, 9, 10, 11, 12}
카드 3에는 {1, 2, 5, 6, 9, 10, 13, 14}
카드 4에는 {1, 3, 5, 7, 9, 11, 13, 15}가 있다.

String answer 'Y'혹은 'N'으로 구성된 길이 4의 문자열 (Hanako의 대답)
return int number (Hanako가 고른 숫자)

Example Data

0)
answer = "YNYY"
returns: 5

1)
answer = "YNNN"
returns: 8

2)
answer = "YYYY"
returns: 1

3)
answer = "NYNY"
returns: 11

Solve

1~16은 1~4번 숫자 카드에서 각 숫자 별 포함/비포함 패턴에 각자 대응된다
e.g. 숫자 1은 숫자카드 1~4에 다 포함되어 있으므로 "YYYY"라는 대답을 할 것이다

각 대답 문자열을 1~16까지 대응시켜, answer로 주어진 문자열에 매핑된 숫자를 찾아내면 된다

public class NumberMagicEasy{

    public int theNumber(String answer){
        int ret = 0;
        //각 대답을 각 리프 노드에 매핑시키자
        String[] allAns = { "YYYY", "YYYN", "YYNY", "YYNN", //1~4
                            "YNYY", "YNYN", "YNNY", "YNNN", //5~8
                            "NYYY", "NYYN", "NYNY", "NYNN", //9~12
                            "NNYY", "NNYN", "NNNY", "NNNN" }; //13~16

        //idx로 정답 숫자를 찾아내자
        for(int i=0; i<allAns.length; i++){
            if(allAns[i].equals(answer)) ret = i+1;
        }

        return ret;
    }
}