[PCCP] 4회차 : BFS & DFS

교육 프로그램명 : 혁신융합대학 프로그래머스 PCCP(Python) 대비 교육

교육 일시 : 2023.08.24 10:00~15:00

강사명 : 김태원 강사님

 

 

1. BFS

2. DFS

 

---

1. BFS

- 큐 자료형을 이용해 구현

- 시작 노드에서 가까운 노드들부터 우선 방문하는 방식

  => 최단거리 or 최소 횟수문제, 특정 지점에 도착하는 최소경로 or 최거리를 구하는 문제에서 주로 사용된다.

 

- 연습 문제 : BFS로 이진트리 탐색

- while문 한번마다, Q 내 현재 level의 모든 노드에서, 가능한 다음 노드를 찾아 Q에 넣고, level을 1 증가한다.

from collections import deque

def BFS():
    Q=deque()
    Q.append(1)     # 1 level의 root 노드 Q에 넣기

    while Q:
        n=len(Q)    #현재 level의 노드 개수
        for i in range(n):
            v=Q.popleft()
            print(v, end=" ")
            for nv in [v*2, v*2+1]:     #v의 왼쪽, 오른쪽 자식 index
                if nv > 7:
                    continue
                Q.append(nv)    #다음 level 노드들로 Q 채우기
                  
BFS()

 

- 연습 문제 : 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

- 로봇이 갈 수 있는 곳이 1, 갈 수 없는 곳이 0 이므로 이미 방문한 곳은 0으로 전환한다.

- while문 한번마다, Q 내 현재 level의 모든 노드에서, 가능한 다음 노드를 찾아 Q에 넣고, level을 1 증가한다.

- 각 지점에서 4방향 이동으로 탐색을 진행해 이동할 수 있는 다음 노드를 찾는다.

from collections import deque

def solution(maps):
	# 4방향 이동 list 정의
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]
    
    n = len(maps)		#행 길이
    m = len(maps[0])	#열 길이
    
    Q = deque()
    Q.append([0,0])
    maps[0][0]=0	#이미 방문한 길이면 0으로 전환
    L=1		#level = 해당 지점까지 도달하는데 거리
    
    while(Q):
        for _ in range(len(Q)):	#한 level에 있는 모든 지점에 대하여
            r, c = Q.popleft()	#각 지점을 기준으로
            for i in range(4):	#4방향 이동 탐색 진행
                nr = r+dr[i]
                nc = c+dc[i]
                if 0<=nr<n and 0<=nc<m and maps[nr][nc] == 1:
                    if nr==n-1 and nc==m-1 :
                        return L+1
                    Q.append([nr, nc])
                    maps[nr][nc]=0
        L+=1
        
    return -1	#while문에서 return 되지 않은 경우 길이 없음 -1 출력

 

 

 

2. DFS

- 재귀함수 방식으로 구현

- 시작 노드에서 최대한 많은 가능한 노드까지 (leaf 노드, 모든 노드 등) 탐색하고 돌아오는 방식

  => 모든 노드를 사용하여 가능한 경로 or 조합과 같이 원소를 순서대로 배치하는 문제에서 주로 사용된다.

 

- 연습 문제 : 순열 구하기, 1~n 숫자에서 m개를 순열배치

- 방문 여부를 저장하는 방법으로 check stack 이용

- 방문한 현재 노드 i를 방문 stack에 넣고, 현재 노드를 포함하는 DFS를 진행한다.

  현재 노드 i를 포함하는 DFS가 끝나면 stack에서 i를 제거한다.

def DFS(L, n, m, ch):
    if L == m:		#필요한 만큼 조합이 끝난 경우
        for x in ch:
            print(x, end=" ")
        print()

    else:
        for i in range(1, n+1):
            if i not in ch:
                ch.append(i)		#현재 노드를 stack에 넣기
                DFS(L+1, n, m, ch)	#DFS 진행
                ch.pop()			#현재 노드에 대한 DFS가 끝나는 시점에 다시 빼기
    
            
def solution(n, m):
    ch = [] 	#방문한 노드를 저장하는 stack
    L=0		#level = 현재 노드까지 오는 경로 길이
    DFS(L, n, m, ch)

 

 

- 도전 문제 : 체육대회

https://school.programmers.co.kr/learn/courses/15008/lessons/121684

프로그래머스

- 학생을 각 종목에 배치했을때 ability 합이 최대가 되는 조합을 계산

- 방문 여부를 저장하는 방법으로 check list 이용 (1이면 방문, 0이면 미방문)

- 방문한 현재 노드 i에 대해 list[i]=1로 만들고, 현재 노드를 포함하는 DFS를 진행한다.

  현재 노드 i를 포함하는 DFS가 끝나면 list[i]=0으로 만든다.

- 순열 조합에 학생 추가할 때 sum+추가된 ability를 계산해 함수 인자로 전달

- 순열이 완성되었을 때 global ans보다 크면 ans를 갱신

ans = 0

def DFS(n, m, L, s, ability, check):
    global answer    
    if L == m:
        ans = max(ans, s)
    else:
        for i in range(n):
            if check[i] == 0:
                check[i] = 1
                DFS(n, m, L+1, s + ability[i][L], ability, check)
                check[i] = 0


def solution(ability):
    global ans
    check = [0]*len(ability)
    n = len(ability)        # 학생 수
    m = len(ability[0])     # 종목 개수
    
    DFS(n, m, 0, 0, ability, check)      
    # Level, sum, ability, check
    # L : level = 고른 학생 수, sum : 능력치의 합
    
    return answer