Baekjoon 15649번 N과 M(1), 2566번 최댓값 파이썬 풀이

위 문제는 백트래킹 문제이다. 백트래킹은 DFS(Depth-First Search, 깊이 우선 탐색)의 방식을 기반으로, 불필요한 경우를 배제하며 원하는 해답에 도달할 때까지 탐색하는 전략이다.

DFS를 기반으로 두고 있기 때문에 스택(Stack)을 이용해 퇴각을 하며 다음 탐색을 진행하기 때문에 백트래킹(또는 퇴각검색)이라 불린다.

백트래킹은 기본적으로는 모든 경우의 수를 탐색한다는 브루트 포스(Brute Force) 전략을 취하지만, 처리 속도를 향상시키기 위한 가지치기(Pruning)가 중요한 역할을 한다.

n, m = map(int, input().split())

s = []
def f():
  if len(s) == m:
    print(' '.join(map(str, s)))
    return

  for i in range(1, n + 1):
    if i in s:
      continue
    s.append(i)
    f()
    s.pop()

f()

여러번 반복을 돌면서 스택에 값을 push하고 함수가 끝난 후에는 나와야 하기 때문에 pop을 해준다.

항상 1부터 N까지의 자연수를 모두 순회하면, 이미 선택한 숫자를 또 선택해가며 의미없는 작업을 반복한다.
그래서 이미 선택한 숫자를 다시 선택하려 하면 배제하는 방식으로 가지치기를 해준다.

 

---

table = [list(map(int, input().split())) for _ in range(9)]

max_num = 0
max_row, max_col = 0, 0
for row in range(9):
    for col in range(9):
        if max_num <= table[row][col]:
            max_row = row + 1
            max_col = col + 1
            max_num = table[row][col]

print(max_num)
print(max_row, max_col)

이번 코드는 크게 어렵지 않았다. 2차원 리스트 입력받고 하나하나 대조해가며 최댓값을 찾게 했다. 당연히 변수 max를 0으로 초기화했다.