★Backtracking Upper-Intermediate I - 9 Solved★

★ 15663 N과 M (9) ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
num,visited=[],[False]*N
def track():
    if len(num)==M:
        print(*num)
    else:
        last=0
        for i in range(len(nums)):
            if not visited[i] and last!=nums[i]:
                visited[i]=True
                num.append(nums[i])
                last=nums[i]
                track()
                num.pop()
                visited[i]=False
track()

 

---

★ 15664 N과 M (10) ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
num,visited=[],[False]*N
def track():
    if len(num)==M:
        print(*num)
    else:
        last=0
        for i in range(len(nums)):
            if last!=nums[i] and not visited[i]:
                if (len(num)==0) or (len(num)>=1 and num[-1]<=nums[i]):
                    visited[i]=True
                    num.append(nums[i])
                    last=nums[i]
                    track()
                    num.pop()
                    visited[i]=False
track()

---

★ 15665 N과 M (11) ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
num=[]
def track():
    if len(num)==M:
        print(*num)
    else:
        last=0
        for i in range(len(nums)):
            if last!=nums[i]:
                num.append(nums[i])
                last=nums[i]
                track()
                num.pop()
track()

---

★ 15666 N과 M (12) ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
num=[]
def track():
    if len(num)==M:
        print(*num)
    else:
        last=0
        for i in range(len(nums)):
            if last!=nums[i]:
                if len(num)==0 or (len(num)>=1 and num[-1]<=nums[i]):
                    num.append(nums[i])
                    last=nums[i]
                    track()
                    num.pop()
track()

 

🎞️ N과 M 문제는 백트래킹 포스팅 참조

---

★ 6603 로또 ★

import sys
input=sys.stdin.readline

def track(arr,ans,N):
    if len(ans) == 6:
        print(*ans)
    else:
        for i in range(N):
            if len(ans)==0 or (len(ans)>=1 and ans[-1]<arr[i]):
                ans.append(arr[i])
                track(arr,ans,N)
                ans.pop()

while 1:
    inp=list(map(int,input().split()))
    N=inp[0]
    if N == 0:
        break
    track(inp[1:],[],N)
    print()

 

🎞️ 오름차순으로 수열이 주어지므로 오름차순 조건으로 구한 수열이 로또 경우의 수. 길이가 6이면 바로 출력.

---

★ 1182 부분수열의 합 ★

 

import sys
input=sys.stdin.readline
N,S=map(int,input().split())
nums=list(map(int,input().split()))
ans=[]
cnt=[]

def track(start):
    if len(ans)>=1 and sum(ans) == S:
        cnt.append(tuple(ans))
    
    for i in range(start,N):
        ans.append(nums[i])
        track(i+1)
        ans.pop()

track(0)
print(len(cnt))

 

🎞️ combinations 형태로, 조합론이 아닌, backtracking으로 접근한다면 매 for문 돌릴 때 마다 내 위치 기준 맨 오른쪽 원소까지만 돌면 되므로 track() 인자에 시작 index 설정. 재귀로 track() 돌 때 track(i+1)로 start index부터 for문 돌리기

---

★ 14888 연산자 끼워넣기 ★

 

import sys
input=sys.stdin.readline

def operation(x,y,kind):
    if kind == '+':
        x+=y
    elif kind == '-':
        x-=y
    elif kind == '*':
        x*=y
    else: #kind == '//'
        if x > 0:
            x//=y
        else: #minus
            x=-((-x)//y)
    return x

def track(level,cursum):
    global cur_max, cur_min
    if level == (N-1): #ready for operation
        cur_max=max(cur_max,cursum)
        cur_min=min(cur_min,cursum)
        return
    
    #
    for i in range(len(ops)):
        if not visited[i]:
            visited[i]=True
            track(level+1,operation(cursum,A[level+1],ops[i]))
            visited[i]=False


N=int(input())
A=list(map(int,input().split()))
p,mi,mul,s=map(int,input().split())
ops='+'*p+'-'*mi+'*'*mul+'/'*s
cur_max,cur_min=-1_000_000_001,1_000_000_001
visited=[False]*(N-1)
ops_final=[]
track(0,A[0])
print(cur_max)
print(cur_min)

 

🎞️ DFS의 성질 활용 문제. 여러 연산자를 딱 1번씩 모두 써야 하므로 visited [] 활용 / track()에 level과 cursum 인자로 넣어서 깊이 level이 N-1이 되었을 때 모든 연산을 활용하였으므로 최댓값/최솟값 update. track() 종료 조건을 DFS의 depth를 활용하는 유형

---

★ 14889 스타트와 링크 ★

 

import sys
input=sys.stdin.readline

N=int(input())
S=[list(map(int,input().split()))for _ in range(N)]
ans=10000
visited=[False]*N
def track(level,start):
    global ans
    if level == N//2: #if full
        a,b=0,0
        for x in range(N):
            for y in range(x+1,N):
                if visited[x] == visited[y] == True: #included in team A
                    a += S[x][y]
                    a += S[y][x]
                elif visited[x] == visited[y] == False: #not included in team B
                    b += S[x][y]
                    b += S[y][x]
        ans = min(ans,abs(a-b))
        return
    #if not full, need more in team A
    for i in range(start,N):
        if not visited[i]:
            visited[i] = True #if True, included in team A
            track(level+1,i+1)
            visited[i] = False

track(0,0)
print(ans)

 

🎞️ 1팀만 인원이 정해지면 visited True, 2팀은 자동으로 visited False일 때 구해서 ans update / 시간 단축을 위해 track()의 두번째 인자 시작 학생 번호는 start+1이 아닌 i+1. visited[x]와 visited[y] 판별 시 for y in range(x+1,N)으로 돌려 (대칭이므로) [x][y] / [y][x] 한번에 합 구하기 / 1팀 인원이 정해지는 경우만 tracking

---

★ 26170 사과 빨리 먹기 ★

import sys
input=sys.stdin.readline

board,visited=[],[[False]*5 for _ in range(5)]
for _ in range(5):
    board.append(list(map(int,input().split())))
start_x,start_y=map(int,input().split())
dx,dy=[0,0,-1,1],[-1,1,0,0]
path=[(start_x,start_y)]
pos_depths=[]
def track(x,y,num_apples,path):
    if num_apples == 3:
        pos_depths.append(len(path)-1)
    else:
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<5 and 0<=ny<5:
                if board[nx][ny] != -1 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    if board[nx][ny] == 1: #if apple
                        board[nx][ny] = -1
                        num_apples+=1
                        path.append((nx,ny))
                        track(nx,ny,num_apples,path)
                        num_apples -= 1
                        board[nx][ny] = 1
                    else: #board[nx][ny] = 0
                        board[nx][ny] = -1
                        path.append((nx,ny))
                        track(nx,ny,num_apples,path) 
                        board[nx][ny] = 0
                    path.pop()
                    visited[nx][ny] = False
board[start_x][start_y] = -1
visited[start_x][start_y] = True
track(start_x,start_y,0,path)
if len(pos_depths)>0:   
    print(min(pos_depths))
else:
    print(-1)

 

🎞️

① visited & 배열을 벗어나지 않는 조건이라면 dfs 진행.

② apple 있다면 num_apples += 1하고 track(), 없다면 바로 track() 

③ num_apples, path dfs 진행하면서 update + board[nx][ny] = -1로 장애물로 update

④ track() 종료 이후 나오면 (1) board[nx][ny] 값 원래 0 또는1로 설정 / (2) 사과 있던 곳이라면 num_of_apples -= 1 / (3) path.pop()으로 path에서 맨 마지막 것 꺼내기 / (4) visited False 설정으로 되돌리기 (backtracking은 함수 이후 후 처리 - 원래로 돌아가게 하는 코드 꼭 필요!)

⑤ track() 초반에 num_apples = 3이라면 바로 path의 길이 - 1로 pos_depths에 update. pos_depths의 최솟값 출력

 

★ BFS 접근법이 안되는 이유: 문제의 특성상, 한 번 지난 곳은 장애물로 처리해서 지나갈 수 없게 했으므로 각 경로를 끝까지 다 조사하고, 바로 앞 경로 - 앞 경로 - 앞 경로 ... 이렇게 깊이있게 + 백트래킹 기법으로 조사해주어야 한다.

---