완전 탐색(Brute-force Search)

완전 탐색(Brute-force Search) 알고리즘 문제

알고리즘 해결 전략 1권 p.157

• 소풍을 간 학생들을 두 명씩 짝 지어 행동하게 하려 한다.
• 서로 친구인 경우에만 짝을 지어야 한다.
• 서로 친구인 경우의 쌍이 주어질 때,
• 학생들을 짝 지을 수 있는 방법의 수를 구현해보자.
• 데이터 개수 n은 항상 짝수이다.

  # 조건
  n = 4
  friends = [[False for _ in range(n)] for _ in range(n)]
  friends[0][1] = friends[1][0] = True
  friends[1][2] = friends[2][1] = True
  friends[2][3] = friends[3][2] = True
  friends[3][0] = friends[0][3] = True
  friends[0][2] = friends[2][0] = True
  friends[1][3] = friends[3][1] = True
  has_pair = [False for _ in range(n)]
  
  # 재귀에서 가장 중요한 것은 계산되는 데이터의 개수가 점점 줄어들어야 한다는 것이다.
  def solve(has_pair):
      # base case
      first = None
      for i in range(n):
          if has_pair[i] == False:
              first = i
              break
              
      if first == None:
          return 1
      
      ret = 0
      for student in range(first+1, n):
          if has_pair[student] == False and friends[first][student] == True:
              has_pair[student] = has_pair[first] = True
              ret += solve(has_pair)
              has_pair[student] = has_pair[first] = False
      
      return ret
  
  # test code
  if __name__ == "__main__":
      solve(has_pair)

알고리즘 해결 전략 1권 p.159

• 게임판 덮기(board cover)
• H x W의 보드가 검은색과 흰색으로 채워져 있다.
• 모든 흰 칸을 L자 모양의 흰색 블록으로 덮고 싶다.
• 블록은 회전 가능하지만 겹치거나 검은색을 침범하거나 밖으로 나가서는 안된다.
• 보드가 있을 때 이를 덮는 방법의 수를 구현해보자.

  # 조건
  H = 8
  W = 10
  board = [
      [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
      [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 
  ]
  
  # L자 블록의 4가지 경우
  cases = [
      [[1, 0], [0, 1], [0, 0]],
      [[0, 1], [1, 1], [0, 0]],
      [[1, 0], [1, 1], [0, 0]],
      [[1, 0], [1, -1], [0, 0]]
  ]
  
  # (y, x) 위치가 보드를 벗어났는지를 판단하는 함수
  def in_range(y, x):
      if y < 0 or x < 0 or y >= H or x >= W:
          return False
      return True
  
  # (y, x)에 c 타입의 블록을 넣는 함수
  def put(y, x, c):
      # c : 블록 타입
      ret = True
      for point in c:
          _y = y + point[0]
          _x = x + point[1]
          if not in_range(_y, _x):
              ret = False
          else:
              board[_y][_x] += 1
              if board[_y][_x] > 1:
                  ret = False
      return ret
  
  # (y, x)에서 c 타입의 블록을 빼는 함수
  def get(y, x, c):
      for point in c:
          _y = y + point[0]
          _x = x + point[1]
          if not in_range(_y, _x):
              continue
          else:
              board[_y][_x] -= 1
  
  def solve():
      # base case
      fx = fy = None
      for i in range(H):
          for j in range(W):
              if board[i][j] == 0:
                  fy = i
                  fx = j
                  break
              
          if fx != None:
              break
      
      if fx == None:
          return 1
      
      ret = 0
      
      for c in cases:
          if put(fy, fx, c):
              ret += solve()
          get(fy, fx, c)
          
      return ret
  
  # test code
  if __name__ == "__main__":
      solve()