백트래킹 - 백준 9663, 2580, 14888, 14889

백트래킹이란 해를 추적하다가 정답이 아니면 다시 되돌아가서 해를 찾는 기법입니다

그만큼 조건을 잘 설정해주는 것이 문제 해결의 핵심 포인트입니다.

 

이번에 문제를 풀면서 정말 문제다운 문제를 푼 느낌이였습니다..혼자서 몇 시간을 고민한 것도 있고

풀이를 보고 가이드만 눈에 익힌 채 코드를 작성하면서 풀어낸 문제도 있습니다...

Silver단계까지는 그나마 노오오력을 하면 풀만 한데

골드 문제는 역시나 아직 조금 버겁네요... 더 열심히 공부해야겠습니다..!!

그럼 이번에도 문제들을 리뷰하면서 마치겠습니다.

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

#퀸은 같은행,열 그리고 대각선에 위치해있으면 공격할 수 있습니다.
#같은 행과 열이 아니고 대각선도 아닌 곳을 찾는 게 문제의 핵심입니다.
import sys
n = int(sys.stdin.readline().rstrip())

#arr에 1차원 배열로 담은 이유는 idx가 체스판의 행이 되고 value가 체스판의 열이 되므로
#1차원 배열로도 퀸의 위치를 알 수 있습니다.
arr = [0] * n #퀸의 갯수
cnt = 0	


def isPending(x) :
	#우리는 0부터 queen을 놓는 방법을 찾고 있으므로 x까지만 검사해주면 됩니다.
    for i in range(x) :
    #arr[x] == arr[i]는 같은 열에 있는지 검사하는 것입니다.
    #abs(arr[x] - arr[i]) == abs(x - i)는 대각선에 위치하는지 보는 것인데
    #행의 차이와 열의 차이가 같다면 대각선에 위치해있다고 볼 수 있습니다.
    #따라서 행의 값인x와 i의 차이와 열의 값인arr[x] - arr[i]의 절대값 차를 비교해줍니다.
        if arr[x] == arr[i] or abs(arr[x] - arr[i]) == abs(x - i) :
            return False
    return True

def nQueen(x) :
    global arr
    global cnt
    #n개까지 퀸을 전부 놓았다면 cnt에 1을 더해줍니다.
    if x == n :
        cnt += 1
    else:    
    	#n개까지 퀸을 놓을 것이므로 순회해줍니다.
        for j in range(n) :
        	#(x,j)에 퀸을 우선 놓습니다.
            arr[x] = j
            #그리고 isPending이 True라면 Queen을 놔도 되는 것을 의미합니다.
            if isPending(x) :
                nQueen(x+1)
nQueen(0)
print(cnt)

http://acmicpc.net/problem/2580

2580번: 스도쿠

#같은행, 열, 3x3박스 안에 같은 숫자가 없어야한다.
import sys 
arr = []
blank = []
#입력을 받으면서 빈칸의 index는 blank에 따로 넣어준다.
for i in range(9) :
    li = list(map(int,sys.stdin.readline().rstrip().split()))
    for j, val in enumerate(li) :         
        if val == 0 :
            blank.append([i,j])
    arr.append(li)
#행 검사
def inRow(num,idx) :
    for i in range(9) :
        if arr[idx][i] == num :
            return False
    return True
#열 검사
def inCol(num,idx) :
    for i in range(9) :
        if arr[i][idx] == num :
            return False
    return True  
#box 검사
def inrect(num,x,y) :
    getX = (x//3) * 3
    getY = (y//3) * 3
    for i in range(getX,getX + 3):
        for j in range(getY,getY + 3) :
            if arr[i][j] == num :
                return False
    return True

def dfs(dep) :
	#깊이가 blank배열과 같으면 모두 채워 넣은 것으로 간주하여 출력
    if dep == len(blank):
        for i in arr :
            print(*i)
    #exit가 아닌 return으로하면 모든 정답을 출력하므로 주의
        exit(0)
        
    for i in range(1,10) :
        x,y = blank[dep][0],blank[dep][1]
        #위 세 함수를 모두 만족하면 arr[x][y]에 해당 값 대입
        if inRow(i,x) and inCol(i,y) and inrect(i,x,y) :
            arr[x][y] = i
            dfs(dep+1)
            arr[x][y] = 0
dfs(0)

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

def plus(a,b) :
    return a+b

def subtract(a,b) :
    return a-b

def multiply(a,b) :
    return a*b

def divide(a,b) :
    if a < 0 :
        share = (-a)// b
        return -share 
    else :
        share = a//b
        return share

cnt = int(input())
#숫자 입력받기
num = list(map(int,input().split()))
sign = ['p','s','m','d']
signCnt = list(input().split())
signList = []
#signList에 signCnt만큼 sign기호 넣어주기
for i in range(4) :
    for j in range(int(signCnt[i])) :
        signList.append(sign[i])
#dfs에 사용할 visit list        
visit = [False] * len(signList)
#최대값,최소값 설정
minNum = 10 **9
maxNum = -10 **9

def calculate(val, a, b) :
    n = 0
    if val == 'p':
        n = plus(a,b)
    elif val == 's' :
        n = subtract(a,b)
    elif val == 'm' :
        n = multiply(a,b)
    elif val == 'd' :
        n = divide(a,b)
    return n

def dfs(dep, arr, n) :
    global minNum
    global maxNum
    #signList에 끝까지 오면 전달받은 n을 maxNum과 minNum에 대입
    if dep == len(signList) :
        if n > maxNum :
            maxNum = n
        if n < minNum :
            minNum =n
        return
	
    for i, val in enumerate(signList) :
        if visit[i] == True :
            continue
        arr.append(val)
        visit[i] = True
        a = n
        b = num[dep+1]
        res = calculate(val,a,b)
        dfs(dep+1,arr,res)
        arr.pop()
        visit[i] = False
dfs(0,[],num[0])
print(maxNum)
print(minNum)

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

from itertools import combinations
n= int(input()) #인원수
people = set([i for i in range(n)]) #사람Set
ability = [list(input().split()) for _ in range(n)] #능력표

allTeam = list(combinations(people,n//2)) #조합으로 모든 팀 조합 받기
realteam = allTeam[:len(allTeam)//2] #조합 생성 중 먼저 생성된 팀이 곧 상대 팀이므로 상대팀을 생성하는 과정인 절반을 없앤다

gap = 0
for i in range(len(realteam)) :
    ateam = set(realteam[i]) #팀나누기
    bteam = people - ateam	#팀나누기
    ateamList = list(ateam)
    bteamList = list(bteam)
    aTeam = 0	#A팀 능력치
    bTeam = 0	#B팀 능력치
    for j in range(len(ateam)) :
        for k in range(len(ateam)) :
            aTeam += int(ability[ateamList[j]][ateamList[k]]) #A팀의 능력치총합
            bTeam += int(ability[bteamList[j]][bteamList[k]]) #B팀의 능력치총합
    result = abs(aTeam - bTeam)
    if result == 0 :
        gap = 0
        break
    if i == 0 :
        gap = result
    if result < gap :
        gap = result

print(gap)

마지막 문제는 재귀가 아닌 반복문으로 풀어냈다.. 이게 더 쉬운 것 같아서..ㅎ

코딩테스트를 심사숙고한 끝에 풀어내면 왠지 모를 짜릿함이 있다.

이게 PS를 하는 매력인 것 같다...

가끔 코드를 작성하고 남들이 더 짧고 간결하게 작성한 코드를 보며 흠칫 놀라기도 하는데

간결한 것도 좋지만 이해하기 쉬운 코드를 작성하기 위해 노력해야겠다!