기본적인 접근: 모든 경우를 탐색한다.
우선 문제 별로 '경우'를 정의한다. 좀 더 풀어서 말하면 '어떻게 해야 한 가지 경우가 완성되는지'를 정의한다.
그 다음 "어떻게 하면 가능한 모든 경우를 만들어낼 수 있을 것인가"를 고민한다.
모든 경우를 만들어 내는 방법에는 크게 세 가지가 있었다.
- itertools 라이브러리 사용
- n중 for문(itertools 대체)
- dfs
dfs의 깊이가 깊어지고, 한 dfs 당 시간복잡도가 증가하면 가지치기를 해줘야 시간 내에 통과할 수 있다.
이때부턴 대개 백트래킹 문제로 분류되는 것 같다.
2309 일곱 난쟁이
경우: 9명의 난쟁이 중 7명의 난쟁이를 고르면 한 가지 경우가 완성.
반대로 생각했을 때, "제외할 2명의 난쟁이"를 골라도 한 가지 경우가 완성된다.
N=9
풀이1(itertools 사용)
itertools 의 combinations을 사용하면 7명의 난쟁이를 쉽게 고를 수 있다.
from itertools import combinations
import sys
heights = []
for i in range(9):
heights.append(int(sys.stdin.readline()))
for cbn in combinations(heights,7):
if sum(cbn)==100:
for val in sorted(cbn):
print(val)
exit(0)풀이2(itertools 사용X)
itertools없이 2중 for문으로 뺄 난쟁이 두 명을 고를 수 있다.
import sys
arr = [int(sys.stdin.readline()) for _ in range(9)]
for i in range(9):
for j in range(i+1,9): # 조합이므로 i+1부터 시작
if sum(arr)-(arr[i]+arr[j])==100:
a = arr[i] # 배열에서 연속 두 번 원소 제거 시 인덱스가 바뀌므로 값을 저장해뒀다가 remove 사용해 삭제
b = arr[j]
arr.remove(a) # remove: 값으로 삭제, pop: 인덱스로 삭제
arr.remove(b)
print('\n'.join(map(str,sorted(arr))))
exit(0)포인트
- for문으로 조합을 구현할 때에는 2번째 for문의 range가 0이 아닌 i+1부터 시작해야 한다. 그렇지 않으면 순서만 다르고 구성 요소는 같은 경우 를 탐색하게 된다.
- 답이 여러 개인데 한 개만 출력하면 되는 경우 처음 답 출력 후 exit(0)로 함수를 종료시킨다.
1182 부분수열의 합
크기가 1인 부분수열~크기가 N인 부분수열 중 원소 합이 S가 되는 경우의 수를 구하면 된다.
경우: N개의 정수 중 k개의 정수를 고르면 한 가지 경우가 완성된다.
이때 k:부분수열의 크기, 1<=k<=N
이렇게 생각해서 k=1인 경우부터 k=N인 경우를 각각 생각하려고 했는데, 찾아보니 좀 더 쉬운 접근이 있었다.
N개의 원소가 있다고 하면, 각 원소 별로 두 가지의 선택지가 있다.
0: 고르지 않는다. 1: 고른다.
N개의 원소가 모두 선택을 하면 한 경우가 완성된 거다!라고 생각하면 쉽다.
N개 원소가 모두 1을 선택했으면 N개짜리 부분수열이 되는 거고, 모두 0을 선택했으면 0개짜리 부분수열이 된다.
1<=N<=20 이므로 O(2^N)이어도 1억번을 넘지 않는다.
풀이
import sys
N, S = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))
cnt=0
def dfs(i,csum): # i:idx, csum: current sum
global cnt
if i==N:
if csum==S:
cnt+=1
else: # for문 대신 고른다/안고른다 두 가지 경우에 대해 dfs호출
dfs(i+1,csum)
dfs(i+1,csum+arr[i])
dfs(0,0)
if S==0: cnt-=1
print(cnt)포인트
모든 경우를 탐색해야 하는 경우, 혹은 탐색하더라도 시간이 넉넉할 만큼 입력이 작은 경우에는 백트래킹이 아닌 일반 dfs를 사용해도 된다. 넣어주고, 되돌려주는 작업에서 코드가 복잡해지고 풀이 시간이 길어진다.
특히 이 문제의 경우 전부 탐색하지 않으면 답을 구할 수가 없다.
완전 탐색=백트래킹이 아니라는 점을 기억할 것!
완전 탐색은 그저 모든 경우를 탐색하는 문제 유형일 뿐이다. 그건 dfs로 충분하다.
2580 스도쿠
풀이
경우: 모든 빈 칸을 채워야 한 가지 경우가 완성된다.
현재 i번째 빈칸까지 채운 상황.
i+1번째 빈칸에 올 수 있는 수는 1~9가 있다. => for문으로 탐색
가능한 수에 대해 그 다음 dfs를 호출한다.
스도쿠 빈칸 개수 최대 64개. 빈 칸마다 1~9를 탐색.
import sys
board = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
blanks = []
for i in range(9):
for j in range(9):
if board[i][j]==0:
blanks.append((i,j))
def check_row(x,r): # 가로 방향 확인
for i in range(9):
if board[r][i]==x:
return False
return True
def check_col(x,c): # 세로 방향 확인
for i in range(9):
if board[i][c]==x:
return False
return True
def check_sqr(x,r,c): # 3*3 정사각형 확인
nr = r//3 * 3
nc = c//3 *3
for i in range(nr,nr+3):
for j in range(nc,nc+3):
if board[i][j]==x:
return False
return True
def dfs(idx):
# idx번째 빈칸까지 채워진 상태, 해당 함수에서 idx+1번째 빈칸에 들어갈 수를 찾을 것
if idx==len(blanks):
for i in range(9):
print(' '.join(map(str,board[i])))
exit(0)
r,c = blanks[idx]
for k in range(1,10):
if check_row(k,r) and check_col(k,c) and check_sqr(k,r,c):
board[r][c]=k
dfs(idx+1)
board[r][c]=0
dfs(0)이렇게 적어놓으니 간단한데 무척 헤맸던 문제.. 거의 세 시간 가량을 붙잡고 있었지만 못 풀었음 😭
실패 요인
여지껏 빈칸이 어떤 수로 채워졌었는지를 기록하기 위해 별도의 딕셔너리를 쓰려고 했다.
딕셔너리를 쓰려고 했던 이유는 1~9 중 들어갈 수 있는 수를 탐색하기 위해 가로, 세로, 사각형을 탐색할 때 좌표를 사용해서 O(1)로 값을 얻어내고 싶어서... 가능은 했을 것 같은데 끝까지 디버깅이 안됐다.
포인트
- 경로를 기록하기 위해 새로운 자료구조를 선언하기 보단 기존 자료구조를 사용하는 법을 우선적으로 고민할 것. 잘 넣고 잘 빼주기만 하면 문제될 게 없다.
- 스도쿠 문제나 N-Queen 문제처럼 특정 좌표의 가능 여부를 판단하기 위해 여러 방향을 확인해야 하는 경우(가로, 세로, 대각선 등) 이를 한 번에 확인하려고 하면 코드가 복잡해진다. 방향을 나눠서 확인하는 게 좋다.
14889 스타트와 링크
4<=N<=20 이다.
풀이
경우: 세 명을 뽑으면 한 가지 경우가 완성된다. 나머지 세 명이 자동으로 한 팀이 된다.
import sys
N = int(sys.stdin.readline())
board = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
selected=[False]*N
ans = 10000000
def dfs(idx,k):
# idx번째 선수까지 뽑은 상태, 해당 함수에서 idx+1번째 선수를 정할 예정
# idx번째 선수의 인덱스는 k
global ans,selected
if idx==N//2:
a,b=0,0
for i in range(N):
for j in range(i+1,N):
if selected[i] and selected[j]:
a+=(board[i][j]+board[j][i])
elif not selected[i] and not selected[j]:
b+=(board[i][j]+board[j][i])
ans = min(ans, abs(a-b))
return
for i in range(k+1,N): # 그 다음 선수는 k+1에서부터 찾아야 함
if not selected[i]:
selected[i]=True
dfs(idx+1,i)
selected[i]=False
dfs(0,0)
print(ans)포인트
- 순서만 다르고 구성요소가 같은 경우를 탐색하지 않기 위해 이미 뽑은 선수보다 뒷쪽에 있는 선수만을 뽑아야 한다.
for i in range(N)이 아닌for i in range(k+1,N). 이걸 위해 dfs함수의 인자 k를 두었다. - 백트래킹에서 넣어주기, 되돌려주기는 for 문 안에서 하자.
def dfs(idx,k): # idx번째 선수로 k번 선수를 고르기
if idx==N/2:
cal_sub()
return
selected[k]=1
for i in range(k+1,N):
if not selected[i]:
dfs(idx+1,i)
if idx+1==N/2:
break
selected[k]=0원래 이렇게 for문 밖에서 표시해준 후 for문 밖에서 표시를 해제하는 방식과 혼용해서 썼었는데, 코드가 지저분하고 자꾸 오류가 난다.
위 방식은 dfs 호출 시 "idx번째 선수로 k번 선수를 고를게~" 하고 넘겨주면
dfs 내에서 표시하고, for문 돌린 다음 for문이 모두 종료되면 해제해주는 식이다.
바람직한 방식은 dfs 호출 시에 이미 표시를 하고, "idx번째 선수로 k번 선수를 골랐어!" 하는 식이다. 백트래킹 관련된 모든 처리를 하고, 그 다음에 다음 dfs를 호출한다.
14500 테트로미노⭐️
백트래킹 이해하는데 매우 도움 된 문제.
4<=N,M<=500
N이 커졌다!
(0,0)~(N-1,M-1)을 차례대로 테트로미노의 첫 좌표로 설정한다고 하면 대략 O(N^2). 각 칸에서 dfs를 호출해야 하므로... 정확한 계산은 모르긴 몰라도 가지치기가 필요해 보인다!
풀이
기괴하게 생겼지만 dfs로 풀 수 있는 문제였다.
경우: 변끼리 이어져 있는 블록 4개를 고르면 한 가지 경우 완성
변끼리 이어져 있어야 하기 때문에, 현재위치에서 상,하,좌,우로 이동할 수 있다.
가지치기 방법: 아직 고르지 않은 블록들이 모두 보드판의 최댓값이라고 가정해서 계산을 해봐도 여태까지 나온 최댓값보다 작다면 탐색을 멈춘다.
예외 케이스: 'ㅜ'모양의 경우 일반적인 dfs로 구현할 수 없다. s==2일 때, 세번째 블록으로 (nr,nc)를 골랐지만 dfs 호출은 dfs(s+1,sum+board[nr][nc],nr,nc)가 아닌 dfs(s+1,sum+board[nr][nc],r,c)로 한다. 이렇게 되면 (r,c)를 기준으로 네 번째 블록을 탐색하게 되므로 'ㅗ'와 같이 양쪽으로 뻗어나간 모양을 만들 수 있다.
이것 또한 넣어주기,돌려주기를 for문 안에서 해야지만 가능했던 구현이라고 생각한다. 암튼 앞으로 백트래킹 할 때는 이 패턴을 유지하는 걸로.
import sys
N,M = map(int,sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
vst = [[0]*M for _ in range(N)]
max_val = max(map(max,board))
ans = -1
# s번째 블록의 위치가 (r,c). 여태 총합이 sum
# s+1번째 블록의 위치를 탐색하는 함수
def dfs(s,sum,r,c):
global ans
dr = [-1,1,0,0]
dc = [0,0,-1,1]
# 종료 조건 1: 남은 개수의 블록이 모두 보드판의 최댓값이라고 가정해도 현재 ans 보다 작다면 탐색 중지
if sum+(4-s)*max_val<=ans:
return
# 종료 조건 2: 4번째 블록 위치까지 결정된 경우 탐색 중지
if s==4:
ans = max(ans,sum)
return
# (r,c)에서 상,하,좌,우 네 방향 탐색
for dr,dc in zip(dr,dc):
nr = r+dr
nc = c+dc
if nr>=0 and nr<N and nc>=0 and nc<M and not vst[nr][nc]:
if s==2:
vst[nr][nc]=True
dfs(s+1,sum+board[nr][nc],r,c) # (nr,nc)가 아닌 (r,c)에서 다음 단계 탐색
vst[nr][nc]=False
vst[nr][nc]=True
dfs(s+1,sum+board[nr][nc],nr,nc) # (nr,nc)서 다음 단계 탐색
vst[nr][nc]=False # (nr,nc)서의 탐색이 모두 끝났다면 표시 해제, for문 다음 단계 진행
for i in range(N):
for j in range(M):
vst[i][j]=True
dfs(1,board[i][j],i,j)
vst[i][j]=False
print(ans)포인트
dfs함수의 call signiture를 잘 정의&이해&활용 하는 게 중요한 문제였다.
dfs(s,sum,r,c) = "s번째 블록의 위치가 (r,c). (r,c)를 기준으로 s+1번째 블록의 위치를 결정해라!". 라는 뜻이다.
9663 N-Queen
예전엔 풀이 보고 풀었는데 이번에는 혼자 풀어서 뿌듯했다 ~.~
풀이
import sys
N = int(sys.stdin.readline())
vc = [0]*N # visited column
vdd = [0]*(2*N-1) # visited diagonal down \
vdu = [0]*(2*N-1) # visited diagonal up /
cnt = 0
def dfs(r,c):
global cnt
for j in range(N):
if vc[j] or vdd[(N-1)-(r+1-j)] or vdu[(r+1+j)]: continue
if r+1==N-1:
cnt+=1
return
vc[j]=1
vdd[(N-1)-(r+1-j)]=1
vdu[(r+1+j)]=1
dfs(r+1,j)
vc[j]=0
vdd[(N-1)-(r+1-j)]=0
vdu[(r+1+j)]=0
dfs(-1,-1)
print(cnt)다음 퀸의 위치를 탐색할 때 처음엔 2중 for문을 돌렸다.
그러나 N*N짜리 보드에 N개의 퀸을 놓아야 하므로, 모든 행에 퀸이 하나씩 있어야 한다. 따라서 다음 행에 퀸을 놓을 수 있는지 없는지만 판단하면 된다. 만약 다음 행에 놓을 수 있는 자리가 없다면 그 경로는 가망이 없으므로 버린다.
스도쿠 문제에서 그랬던 것처럼, 퀸을 놓으려고 할 때 / \ | 세 가지 방향을 탐색해야 했기 때문에 각 방향을 따로 관리해 주었다. (vc,vdd,vdu)
열, 대각선에 퀸이 하나라도 있을 경우 그 열과 대각선에 해당하는 좌표에는 더이상 퀸을 놓을 수 없다. 우상향으로 2N-1개, 좌하향으로 2N-1개의 대각선이 존재한다. 좌표 -> 대각선 번호 하는 식을 계산했다. 이 식을 활용해 (i,j)가 속한 대각선 번호를 알아내고, 그 번호에 퀸이 있는지 확인 했다. (vdd, vdu을 확인)
여기서도 마찬가지로 for문 안에서 넣어주기, 되돌려주기를 해줬다.
첫 유형이라 비교 유형이 없어서 감이 잘 안오는데, 몇 가지 유형을 더 풀어보고 Brute force만의 특징을 좀 더 적어보겠다.
- N의 크기가 작다.
