7. 깊이, 넓이 우선탐색 활용

1. 최대점수 구하기(DFS)

결국 1번째 문제를 풀거냐 말거냐, 2번째 문제를 풀거냐 말거냐, ... 의 문제.

def DFS(L, score, time):
    global maxScore
    if time > m:
        return
    if L == n:
        if score > maxScore:
            maxScore = score
    else:
        DFS(L+1, score+a[L][0], time+a[L][1])  # 다음 행으로 넘어갈 때 back하는 효과 / L번째 문제 품
        DFS(L+1, score, time)  # L번째 문제 풀지 않음
        
    
if __name__ == "__main__":
    n, m = map(int, input().split())
    a = []
    for _ in range(n):
        s, t = map(int, input().split())
        a.append((s,t))
    maxScore = 0
    DFS(0, 0, 0)
    print(maxScore)

처음엔 너무 복잡하게 생각했는데, 결국 풀 지 말 지 선택하는 문제라는 걸 듣고 바로 풀 수 있었다.

→ 결국 부분집합 문제

 

이제 DFS에 조금 익숙해진 듯? 이건 되게 쉬웠다.

---

2. 휴가(삼성 SW역량평가 기출문제: DFS 활용)

문제를 읽고 그럼 그냥 일을 하느냐 마느냐 정하면 되는 거 아닌가 싶었다. 근데 위 문제와 달리 상담에 걸리는 시간이 1일 이상인 경우가 많아서, 그 경우를 어떻게 처리하느냐가 문제인 것 같다. 

* 만약 1일에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다.

위 문구가 중요! L을 가지고 이걸 처리할거야.

 

def DFS(L, pay):
    global res
    if L > n:
        return
    if L == n:
        if pay > res:
            res = pay
    else:
        DFS(L+t[L], pay+p[L])  # L번째 상담을 한다 (0부터 시작)
        DFS(L+1, pay)  # L번째 상담을 하지 않는다
        
    
if __name__ == "__main__":
    n = int(input())
    t = []
    p = []
    for _ in range(n):
        a, b = map(int, input().split())
        t.append(a)
        p.append(b)
    res = 0
    DFS(0, 0)
    print(res)

이 문제도 결국 상담을 하느냐, 마느냐의 부분집합 문제. (헐 내가 풀었어.. 감격...)

 

def DFS(L, pay):
    global res
    if L == n+1:
        if pay > res:
            res = pay
    else:
    	if L+t[L] <= n+1:  # 따로 조건을 빼지 않고 여기서 확인
        	DFS(L+t[L], pay+p[L])
        DFS(L+1, pay)
        
    
if __name__ == "__main__":
    n = int(input())
    t = []
    p = []
    for _ in range(n):
        a, b = map(int, input().split())
        t.append(a)
        p.append(b)
    res = 0
    t.insert(0, 0)  # L을 날짜와 맞추기 위해서
    p.insert(0, 0)
    DFS(1, 0)
    print(res)

나는 그냥 인덱스 번호를 0부터 시작해서, 인덱스 0 - 1일, 1 - 2일 이렇게 했는데 강사님은 날짜와 맞추기 위해서 t와 p에 insert해주셨다. 그리고 상담할 수 있는 기간을 넘어가는지 아닌지를 else 문 안에서 확인하셨다는 점이 나와 다르다.

---

3. 양팔저울(DFS)

문제 이해는 됐는데, (□+1):6 이런 경우를 어떻게 계산하고 포함시켜야 되는지 모르겠다.

def DFS(L, sum):
    global res
    if L == k:
        if 0 < sum <= s:
            res.add(sum)
    else:
        DFS(L+1, sum+a[L])  # 추를 저울의 왼쪽에 놓기 (물그릇은 오른쪽)
        DFS(L+1, sum-a[L])  # 추를 저울의 오른쪽에 놓기 (물그릇은 왼쪽)
        DFS(L+1, sum)  # 추를 올리지 않음
        
    
if __name__ == "__main__":
    k = int(input())
    a = list(map(int, input().split()))
    s = sum(a)
    res = set()  # 중복을 피하기 위해 set 자료형 사용
    DFS(0, 0)
    print(s-len(res))

---

4. 동전 바꿔주기(DFS)

def DFS(L, sum):
    global cnt
    if sum > t or L >= coinCnt:
        return
    if sum == t:
        cnt += 1
    else:
        for i in range(k):
            if n[i] > 0:
                n[i] -= 1
                DFS(L+1, sum+p[i])
                n[i] += 1
                DFS(L+1, sum)


if __name__ == "__main__":
    t = int(input())
    k = int(input())
    p = []
    n = []
    for _ in range(k):
        a, b = map(int, input().split())
        p.append(a)
        n.append(b)
    coinCnt = sum(n)
    cnt = 0
    DFS(0, 0)
    print(cnt)

코드를 나 혼자 이렇게 짜봤는데, 실행해보면 답이 118272로 나온다.

cut tech가 부족한가 싶은데 애초에 sum == t 일 때만 cnt가 증가하는데 어떻게 이렇게 값이 크게 나오는지 전혀 모르겠다.

 

상태 트리는 위와 같다.

 

def DFS(L, sum):
    global cnt
    if sum > t:
        return
    if L == k:
        if sum == t:
            cnt += 1
    else:
        for i in range(n[L]+1):
            DFS(L+1, sum+(p[L]*i))


if __name__ == "__main__":
    t = int(input())
    k = int(input())
    p = []
    n = []
    for _ in range(k):
        a, b = map(int, input().split())
        p.append(a)
        n.append(b)
    cnt = 0
    DFS(0, 0)
    print(cnt)

정답 코드이다.

 

def DFS(L, sum):
    global cnt
    if sum > t or L == k:  # 문제 지점
        return
    if sum == t:
        cnt += 1
    else:
        for i in range(n[L]+1):
            DFS(L+1, sum+(p[L]*i))

처음에 DFS 함수를 이렇게 짰는데, L == k인 경우에 위쪽 if문에 먼저 걸리면서 제대로 cnt되지 않는 문제가 발생했었다.

---

5. 동전 분배하기(DFS)

def DFS(L):
    global res, total
    if L == n:
        sTotal = set(total)
        if len(sTotal) == 3:  # 세 사람의 총액은 서로 달라야 한다는 조건
            tmp = max(sTotal)-min(sTotal)
            if tmp < res:
                res = tmp
    else:
        for i in range(3):
            total[i] += coin[L]
            DFS(L+1)
            total[i] -= coin[L]  # back할 때 더했던 금액을 빼주어야 함


if __name__ == "__main__":
    n = int(input())
    coin = [int(input()) for x in range(n)]
    res = 2147000000
    total = [0]*3  # 세 명 각각의 총액
    DFS(0)
    print(res)

상태트리만 잘 그려놓으면 충분히 풀 수 있는 문제.

 

---

6. 알파코드(DFS)

def DFS(L, P):  # L은 알파벳 코드의 인덱스, p는 res 인덱스
    global cnt
    if L == n:
        cnt += 1
        for i in range(P):
            print(chr(res[i]+64), end = '')
        print()
    else:
        for i in range(1, 27):
            if code[L] == i:
                res[P] = i
                DFS(L+1, P+1)
            elif i >= 10 and code[L] == i//10 and code[L+1] == i%10:  # i가 두 자리 숫자일 때
                res[P] = i
                DFS(L+2, P+1)

if __name__ == "__main__":
    code = list(map(int, input()))  # 하나씩 리스트로 받음
    n = len(code)
    code.insert(n, -1)  # 두자리 숫자를 확인할 때 list out of index 오류 방지
    res = [0]*n
    cnt = 0
    DFS(0, 0)
    print(cnt)

어렵다.. 꼭 다시 보기!!!

---

BFS(Breadth-First Search, 너비우선탐색)

gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

· 큐(queue) 자료구조로 구현 가능

· 상태트리 그리기

· 최단경로 탐색에 이용

---

7. 송아지 찾기(BFS: 상태트리탐색)

from collections import deque
MAX = 10000  # 문제 조건 상 최대값
ch = [0]*(MAX+1)  # 방문 여부 체크할 리스트
dis = [0]*(MAX+1)  # 출발지로부터의 거리를 저장할 리스트
s, e = map(int, input().split())
ch[s] = 1  # 출발지는 무조건 방문한 상태
dis[s] = 0
dQ = deque()
dQ.append(s)

while dQ:  # 큐가 비어있으면 멈춤
    now = dQ.popleft()  # first 꺼내기
    if now == e:  # 목적지 발견했을 경우
        break
    for next in(now-1, now+1, now+5):
        if 0 < next <= MAX:
            if ch[next] == 0:  # 방문하지 않은 노드일 경우 방문
                dQ.append(next)
                ch[next] = 1
                dis[next] = dis[now]+1

print(dis[e])

---

8. 사과나무(BFS)

** 섹션 3에도 같은 문제가 있음(이분탐색, 다이아몬드 활용)

 

n이 홀수 → (n//2, n//2)가 정중앙 좌표

 

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ch = [[0]*n for _ in range(n)]  # 방문여부 체크 리스트
sum = 0

Q = deque()
ch[n//2][n//2] = 1
sum += a[n//2][n//2]
Q.append((n//2, n//2))
L = 0

while True:
    if L == n//2:
        break
    size = len(Q)
    for i in range(size):
        tmp = Q.popleft()
        for j in range(4):  # 상하좌우 탐색
            x = tmp[0]+dx[j]
            y = tmp[1]+dy[j]
            if ch[x][y] == 0:
                sum += a[x][y]
                ch[x][y] = 1
                Q.append((x, y))
    '''
    print(L, size)
    for x in ch:
        print(x)
    '''
        
    L += 1

print(sum)

주석처리한 부분을 출력하면 위와 같다. (확인용)

---

9. 미로의 최단거리 통로(BFS 활용)

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

board = [list(map(int, input().split())) for _ in range(7)]
dis = [[0]*7 for _ in range(7)]  # (0, 0)과의 거리를 저장할 리스트(없어도 되지만, 편의상 만들어서 사용)

# 1번만에 방문할 수 있는 곳 다 방문, 2번만에 방문할 수 있는 곳 다 방문 ...

Q = deque()
Q.append((0, 0))
board[0][0] = 1  # 방문한 곳은 1로 바꿔서 벽으로 만들기

while Q:
    tmp = Q.popleft()
    for i in range(4):
        x = tmp[0] + dx[i]
        y = tmp[1] + dy[i]
        if 0 <= x <= 6 and 0 <= y <= 6 and board[x][y] == 0:  # 경계선 밖으로 가지 못하게, 벽이면 가지 못하게
            board[x][y] = 1  # ch 리스트 대신 board를 그대로 이용
            dis[x][y] = dis[tmp[0]][tmp[1]] + 1
            Q.append((x, y))

if dis[6][6] == 0:  # dis[6][6] == 0이라면 도착점이 도착하지 못한 것
    print(-1)
else:
    print(dis[6][6])

---

10. 미로탐색(DFS)

def DFS(x, y):
    global cnt
    if x == 6 and y == 6:
        cnt += 1
    else:
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0 <= xx <= 6 and 0 <= yy <= 6 and board[xx][yy] == 0:
                board[xx][yy] = 1
                DFS(xx, yy)
                board[xx][yy] = 0  # back할 때 다시 체크 풀기 / 중요!


if __name__ == "__main__":
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    board = [list(map(int, input().split())) for _ in range(7)]
    cnt = 0
    board[0][0] = 1  # 첫 출발점 체크 (방문한 곳은 벽으로 만들기)
    
    DFS(0, 0)

    print(cnt)

9, 10번 문제는 혼자 고민해보거나 코드를 보면 이해할 수 있는 수준인 것 같아서 쓸 말이 별로 없다.

 

---

10. 등산경로(DFS)