[백트래킹의 신이 되자] 백준 문제모음

신이 되기에는 터무니없이 적은 문제 양이지만 스리슬쩍 올려봅니다 ^^~

 

<백준의 단계별 풀기를 참고해서 구성해 봤다>

기초

# 백준 15649, 15650, 15651, 15652

- 같은 패턴이 반복되는 N과 M시리즈 문제들

- 백트래킹의 기본 구조(dfs + 탐색 중단조건)을 익히기 좋다.

 

입문

# 백준 1182, 1759, 2661, 1405

- 탐색 중단조건과 정답 판단조건이 조금 복잡화된 문제들

- 조금 더 복잡해 보이지만 기본적인 구조는 같다.

 

심화

# 백준 2580, 9663, 14888, 14889

- 백트래킹인지 아닌지 티가 덜 나는 문제들

- 구조가 약간 다른 것들도 있어서, 상태공간트리를 머릿속으로 그리는 연습을 할 수 있다.

 

문제 해설

기초 문제는 건너뛴다.

1. 입문

    # 1182 부분수열의 합

    1) 백트래킹의 냄새

    - 완전탐색인가? O

    - 일부만 탐색해도 되는가? O : 이전에 뽑은 수들을 순서만 바꿔 뽑는 가지를 탐색하지 않아도 된다.

   2) dfs 로직 구상

       (1) sum이 K와 같고 부분수열의 길이가 양수인 경우, result ++, 리턴

       (2) 지난 검색이 끝난 시점+1부터 각 원소에 대해 해당 원소를 더하고 재귀를 돌린 뒤 다시 해당 원소를 빼준다.

 

    # 1759 암호 만들기 (군대는 안가봤지만 이런 사람을 '폐급'이라고 하는 것인가?! 약간 무섭다.)

    1) 백트래킹의 냄새

    - 완전탐색인가? O

    - 일부만 탐색해도 되는가? O : 오름차순이 아닌 가지를 탐색하지 않아도 된다.

   2) dfs 로직 구상

       (1) 길이 L의 암호를 만든 경우, 1개 이상의 모음과 2개 이상의 자음을 포함하는 경우 출력, 리턴

       (2) 지난 검색이 끝난 시점+1부터(오름차순 정렬해야함) 각 원소에 대해 해당 원소 포함, 재귀, 해당 원소 제거

 

   # 2661 좋은 수열

    1) 백트래킹의 냄새

    - 완전탐색인가? O

    - 일부만 탐색해도 되는가? O : 현 시점에서 나쁜 수열인 가지를 더 이상 탐색하지 않아도 된다.

   2) dfs 로직 구상

       (1) 지금까지 구한 수열이 나쁜 수열이거나 이미 수열을 찾은 경우 return

       (2) 길이가 N인 경우, 해당 수열이 정답이다. 출력 후 return

       (3) 1,2,3 각각에 대해 해당 원소를 더하고 재귀 돌린 후 다시 해당 원소를 빼준다.

   3) Tip : 좋은 수열을 판단하는 방법

   - 1부터 N/2길이를 단위로 겹치는 구간이 있는지 체크하면 된다.

 

   # 1405 미친 로봇

    1) 백트래킹의 냄새

    - 완전탐색인가? O

    - 일부만 탐색해도 되는가? O : 복잡한 경로인 가지를 탐색하지 않아도 된다.

   2) dfs 로직 구상

       (1) 길이가 N인 경우, 해당 경로가 단순한 경로이다. result에 해당 경로를 택할 확률을 더해준다.

       (2) 동,서,남,북 각각의 방향에 대해 해당 방향으로 이동했을 때 복잡한 경로가 되지 않으면 해당 방향을 경로에 추가, 재귀, 다시 뺀다.

   3) Tip : 복잡한 경로를 판단하는 방법

   - 복잡복잡. 지금까지 지나온 지점을 set으로 저장했다.

 

2. 심화

   # 2580 스도쿠

    1) 백트래킹의 냄새

    - 완전탐색인가? O

    - 일부만 탐색해도 되는가? O : 스도쿠의 규칙을 어기는 수를 칸에 적는 가지를 탐색하지 않아도 된다.

   2) dfs 로직 구상

       (1) 모든 칸을 탐색한 경우 결과를 출력하고 return

       (2) 현재 탐색하는 칸에 숫자가 적혀 있으면 다음 칸을 재귀적으로 탐색

       (3) 현재 탐색하는 칸에 숫자가 적혀 있지 않으면 1~9 중 쓸 수 있는 수를 쓰고, 재귀, 수를 지운다.

   3) Tip : 쓸 수 있는 수를 판단하는 방법

   - row, column, 3x3 순으로 판단.

   - 3x3는 해당 좌표가 속하는 3x3 칸의 원점을 찾아 dx,dy로 탐색했다.

 

   # 9663 N-qeens (너무 유명한 문제!! ㅇ0ㅇ)

    1) 백트래킹의 냄새

    - 완전탐색인가? O

    - 일부만 탐색해도 되는가? O : 퀸이 서로를 공격하는 가지를 탐색하지 않아도 된다.

   2) dfs 로직 구상

       (1) 마지막 행까지 퀸을 배치한 경우, return

       (2) 이전에 퀸을 놓은 행 + 1 에서 퀸을 놓을 수 있는 공간 각각에 대해 퀸을 놓고 재귀, 다시 퀸을 지운다.

 

   # 14888 연산자 끼워넣기

   # 14889 스타트와 링크

   - 이 두 문제는 PS 카테고리 내에 해설을 써 뒀다.

 

 

 

<문제 풀면서 느낀점과 배운점>

- 출력 형식이나 소숫점 precision같은 사소한 부분을 조심하자

- 머릿속으로 상태공간 트리를 그리자