영리한 프로그래밍을 위한 알고리즘 강좌 - Ch0.순환 #4~7

섹션 0. 순환(Recursion)

2-1. Recursion의 응용 : 미로찾기

- Recursive Thinking

현재 위치에서 출구까지 가는 경로가 있으려면

1) 현재 위치가 출구이거나 혹은

2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

 

- 미로찾기(Decision Problem [답이 yes or no인 문제])

boolean findPath(x, y)
if (x, y) is the exit // 현재 위치가 출구라면
    return true

else 
    for each neighbouring cell (x', y') of (x, y) do // 인접한 셀 각각에 대해서 
        if (x', y') is on the pathway
            if findPath (x', y')
                return true;
    return false;

이미 가본 위치와 가보지 않은 위치를 구분하는 게 중요

 

boolean findPath(x, y)
    if (x, y) is the exit
        return true

else 
    mark (x, y) as a visited cell;
    for each neighbouring cell (x', y') of (x, y) do
        if (x', y') is on the pathway and not visited
            if findPath(x', y')
                return true;
    return false;

 

 

하지만 이거랑 다른 방식으로 구현할거임

 

boolean findPath(x, y) // 한 셀의 위치를 받아서
    if (x, y) is either on the wall or a visited cell //이미 방문된 셀이라면
        return false; //false return
    else if (x, y) is the exit
        return true;
    else
        mark (x, y) as a visited cell; //이미 방문한 셀이라면
        for each neighbouring cell (x', y') of (x, y) do
            if findPath(x', y')
                return true;
        return false;

recursion 호출 횟수는 많아지지만, 코드가 조금 더 간결해짐

 

- class Maze

 

PATH_COLOR : visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell

BLOCKED_COLOR : visited이며 출구까지의 경로상에 있지 않음이 밝혀진 cell

public class Maze {
  private static int N=8;
  private static int [][] maze = {
    {0, 0, 0, 0, 0, 0, 0, 1},
    {0, 1, 1, 0, 1, 1, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 1},
    {0, 1, 0, 0, 1, 1, 0, 0},
    {0, 1, 1, 1, 0, 0, 1, 1},
    {0, 1, 0, 0, 0, 1, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 1},
    {0, 1, 1, 1, 0, 1, 0, 0}
  };

  private static final int PATHWAY_COLOUR = 0; //white
  private static final int WALL_COLOUR = 1; // blue
  private static final int BLOCKED_COLOUR = 2; // red
  private static final int PATH_COLOUR = 3;  // green
}

 

- 최종 코드

clss Maze

 

public static boolean findMazePath(int x, int y) {
  if (x < 0 || y < 0 || x >= N || y >= N) // 유효한 범위인지 탐색
    return false;
  else if (maze[x][y] != PATHWAY_COLOUR)
    return false;
  else if (x == N-1 && y == N-1) {
    maze[x][y] = PATH_COLOUR;
    return true;
  }
  else {
    maze[x][y] = PATH_COLOUR;
    if (findMazePath(x-1, y) || findMazePath(x, y+1)
      || findMazePath(x+1, y) || findMazePath(x, y-1)) {
        return true;
    }
    maze[x][y] = BLOCKED_COLOUR; //dead end
    return false;
  }
}

// 메인 함수
public static void main(String [] args) {
  printMaze();
  findMazePath(0, 0);
  printMaze();
}

 

 

2-2. Recursion의 응용 : Counting Cells in a Blob

-Binary 이미지가 주어짐

- 각 픽셀은 background pixel이거나 혹은 image pixel

- 서로 연결된 image pixel들의 집합을 blob이라고 부름

- 상하좌우 및 대각방향으로도 연결된 것으로 간주

예시

- 입력 :

N*N 크기의 2차원 그리드(grid)

하나의 좌표(x,y)

 

- 출력:

픽셀 (x,y)가 포함된 blob의 크기

(x,y)가 어떤 blob에도 속하지 않는 경우에는 0

 

현재 픽셀이 이 속한 blob의 크기를 카운트하려면

    현재 픽셀이 image color가 아니라면

        0을 반환한다

    현재 픽셀이 image color라면

        먼저 현재 픽셀을 카운트한다(count = 1)

        현재 픽셀이 중복 카운트되는 것을 방지하기 위해 다른 색으로 칠한다. 

        현재 픽셀에 이웃한 모든 픽셀들에 대해서

            그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다

        카운터를 반환한다

 

- Algorithm for countCells(x,y)

if the pixel (x, y) is outside the grid
    the result is 0;

else if pixel (x, y) is not an image pixel or already counted 
    the result is 0;

else 
    set the colour of the pixel (x, y) to a red colour; // red : 이미 카운트되었음을 표시
    the result is 1 plus the number of cells in each piece of the blob that includes a nearest neighbour;

 

- 최종 코드

 

private static int BACKGROUND_COLOR = 0;
private static int IMAGE_COLOR = 1;
private static int ALREADT_COUNTED = 2;

public int countCells(int x, int y) {
  if (x < 0 || x >= N || y < 0 || y >= N)
    return 0;
  else if (grid[x][y] != IMAGE_COLOR)
    return 0;
  else {
    grid[x][y] = ALREADY_COUNTED;
    return 1 + countCells(x-1, y+1) + countCells(x, y+1)
      + countCells(x+1, y+1) + countCells(x-1, y)
      + countCells(x+1, y) + countCells(x-1, y-1)
      + countCells(x, y-1) + countCells(x+1, y-1);
  }
}

 

2-3. Recursion의 응용 : n queens problem

-Back tracking

-상태공간트리

상태공간트리란 찾는 해를 포함하는 트리.

즉 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함. 따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

상태공간 트리의 모든 노드를 텀색해야 하는 것은 아님

 

- 되추적 기법(BackTracking)

상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘을 말한다.

 

-최종 코드

 int [] cols = new int [N+1];
  boolean queens( int level)
  {
    if (!promising(level))
      return false;
    // success의 경우
    else if (level==N) {
      for (int i = 1; i <=N i++)
        // 말들의 위치를 출력해준다.  
        System.out.printIn("(" + i + ", " + cols[i] + ")");
      return true;
    }
    for (int i = 1; i <= N; i++) {
      cols[level+1] = i;
      if (queens(level+1))
        return true;
    }
    return false;
  }

 

2-4. 멱집합(powerset)

멱집합 : 어떤 집합의 모든 부분집합의 집합

{a,b,c,d,e,f}의 모든 부분집합을 나열하려면

-a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열하고

-{b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다

 

powerSet(S)
if S is an empty set
    print nothing;
else
    let t be the first element of S;
    find all subsets of S-{t} by calling powerSet(S-{t});
    print the subsets;

    print the subsets with adding t;    

-> 미션 : S의 멱집합을 출력하라.

이렇게 하려면 powerSet 함수는 여러 개의 집합들을 return 해야한다.

 

 

powerSet(P, S)
if S is an empty set
    print P;
else
    let t be the first element of S;
    powerSet(P, S-{t});
    powerSet(P ∪ {t}, S - {t});

-> 미션 : S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력하라

recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야한다는 의미이다. 두 번째 집합의 모든 부분집합들에 첫번째 집합을 합집합하여 출력한다.

 

-powerset

private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
private static int n=data.length;
private static boolean [] include = new boolean [n];

public static void powerSet(int k) {
  if (k == n) {
    for (int i = 0; i < n; i++)
      if (include[i]) System.out.print(data[i] + " ");
    System.out.printIn();
    return;
  }
  include[k]=false;
  powerSet(k+1);
  include[k] = true;
  powerSet(k+1);
}

-> 미션 : data[k],...,data[n-1]의 멱집합을 구한 후 각각에 include[i]=true, i=0,...,k-1 인 원소를 추가하여 출력하라

처음 이 함수를 호출할 때는 powerSet(0)로 호출한다. 즉 P는 공집합이고 S는 전체집합이다.

 

 

-상태공간트리(state space tree)

-해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리

- 트리의 모든 노드들을 방문하면 해를 찾을 수 있다.

- 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다

 

private static char data[] = {'a', 'b', 'c', 'd', 'e',};
private static int n = data.length;
private static boolean [] include = new boolean [n];

public static void powerSet(int k) {
  if (k == n) { //만약 내 위치가 리프노드라면
    for (int i = 0; i < n; i++)
      if (include[i]) System.out.print(data[i] + " ");
    System.out.printIn();
    return;
  }
  include[k] = false;
  powerSet(k+1); //먼저 왼쪽으로 내려갔다가
  include[k] = true;
  powerSet(k+1); //이번엔 오른쪽으로 내려간다
}