[Python] 백준 2239, 프로그래머스 피로도

1. 문제: https://www.acmicpc.net/problem/2239

해당 문제는 백트래킹으로 풀이할 수 있다.

- 행과 열에는 1부터 9까지의 수가 들어가야하는데, 다양한 경우의 수가 포함될 수 있으며 조건이 맞으면 return 해야함

 

✅ 풀이

import sys
input = sys.stdin.readline

board = []

for _ in range(9):
  board.append(list(map(int, str(input().rstrip()))))

def valid_in_col(col, num):    # 열에 수가 포함되어있으면 False return
  for i in range(9):
    if board[i][col] == num:
      return False
  return True

def valid_in_row(row, num):    # 행에 수가 포함되어있으면 False return
  for i in range(9):
    if board[row][i] == num:
      return False
  return True

def valid_in_box(row, col, num):      # 행, 열이 속한 3x3 박스에 수가 포함되어있으면 False return
  area_row = (row // 3) * 3
  area_col = (col // 3) * 3
  for i in range(area_row, area_row + 3):
    for j in range(area_col, area_col + 3):
      if board[i][j] == num:
        return False

  return True

def find_zero():             # 0인 좌표를 찾되, 찾을 수 없으면 (-1, -1)을 return한다.
  for i in range(9):
    for j in range(9):
      if board[i][j] == 0:
        return i, j

  return -1, -1

def backtracking():
  x, y = find_zero()
  if (x, y) == (-1, -1):
    for i in range(9):
      for j in range(9):
        print(board[i][j], end = "")
      print()

    sys.exit(0)

  for i in range(1, 10):
    if valid_in_col(y, i) and valid_in_row(x, i) and valid_in_box(x, y, i):
      board[x][y] = i    # 채웠다가
      backtracking()
      board[x][y] = 0    # 원상복구

backtracking()

 

2. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/87946

해당 문제는 백트래킹으로 풀이할 수 있다.

- 근거: 각 던전은 1번만 탐험 가능하다 (=방문 여부 체크), 던전을 방문하는 순서에 따라 이후에 방문할 수 있는 던전이 달라진다 (=가지치기)

 

✅ 풀이

answer = -1

def solution(k, dungeons):
    visited = [False] * len(dungeons)
    
    def dfs(power, num):
        global answer
        
        answer = max(answer, num)   # 탐험할 수 있는 최대 던전 수 갱신
        
        for i in range(len(dungeons)):
            if not visited[i] and power >= dungeons[i][0]:  # 방문하지 않은 던전 중, 현재 피로도에서 방문할 수 있는 던전이라면
                visited[i] = True       # 해당 던전 방문처리 후
                dfs(power - dungeons[i][1], num+1)    # 피로도 소모 및 방문갯수 count + 1
                visited[i] = False      # 해당 던전 방문여부를 복원하여 다른 후보지 탐색
                
    dfs(k, 0)
        
    return answer

 

오늘의 배운점

- 공백없는 정수 문자열을 정수 배열로: list(map(int, str(n)))

* str(n) --> 정수 문자열을 문자열로, map(int, str(n)) --> 문자열을 이루는 각 문자를 정수로 매핑, list(map(int, str(n)) --> 매핑한 정수를 배열화