[PCCP] 5회차 : DFS 활용 & 그래프

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

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

강사명 : 김태원 강사님

 

 

1. DFS 연습 문제

2. 그래프

---

1. DFS 연습 문제

 

연습 문제 : 줄다리기

- fight 정보 = 학생 index 쌍 (i, j) list  →  2차원 배열 변환, 사이가 좋지 않은 관계 index를 1로 지정

- 마지막으로 넣은 학생 index p[-1]과 i가 fight 관계이면 해당 case는 cutting

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

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

p = []		#학생 index를 저장하는 stack
count = 0	#가능한 순열 조합의 개수

def DFS(L, fight, ch):
    global p, count

    if L == 7:
        count+=1
    else:
        for i in range(7):

            #fight가 1인 case이면 cutting
            if len(p)>0 and fight[p[-1]][i]==1:
                continue
            
            if ch[i]==0:
                ch[i]=1
                p.append(i)
                DFS(L+1, fight, ch)
                p.pop()
                ch[i]=0

    
def solution(nums):
    global count
    count=0

    fight = [[0 for _ in range(7)] for _ in range(7)]
    for n in nums:
        fight[n[0]-1][n[1]-1]=1
        fight[n[1]-1][n[0]-1]=1
    
    ch=[0 for _ in range(7)]
    DFS(0, fight, ch)

    return count

 

 

연습 문제 : 검정색 영역 구하기

- Blood Fill 유형 = 다차원 배열에서 연결된 영역을 찾는 문제

- solution 함수에서 1에 해당하는 지점에 도착하면 DFS를 진행

  → DFS 함수는 4방향 탐색으로 시작점에서 인접한 모든 1을 찾고, 0으로 변환

  → DFS가 끝나면 해당 영역은 모두 0으로 변환 + 영역의 개수 1 증가

ans=0
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def DFS(r, c, board):
    global ans
    for i in range(4):
        nr=r+dr[i]
        nc=c+dc[i]
        if 0<=nr<5 and 0<=nc<5 and board[nr][nc]==1:
            board[nr][nc]=0
            DFS(nr, nc, board)
            

def solution(board):
    global ans
    ans=0
    for i in range(5):
        for j in range(5):
            if board[i][j]==1:
                board[i][j]=0
                DFS(i, j, board)
                ans+=1
    return ans

 

연습 문제 : 영역의 크기

- 영역에 포함된 칸 수 = DFS 호출 횟수

n=0
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def DFS(r, c, board):
    global ans, n
    n+=1
    for i in range(4):
        nr=r+dr[i]
        nc=c+dc[i]
        if 0<=nr<5 and 0<=nc<5 and board[nr][nc]==1:
            flag=1
            board[nr][nc]=0
            DFS(nr, nc, board)
   
    

def solution(board):
	global n
    ans=[]
    
    for i in range(5):
        for j in range(5):
            if board[i][j]==1:
                board[i][j]=0
                n=0
                DFS(i, j, board)
                ans.append(n)
    return ans

 

 

 

 

2. 그래프

- 그래프 구현 1 : 인접 행렬 (2차원 배열)

  모든 원소가 0인 2차원 배열  →  (i, j) egde가 존재하면 graph[ i ][ j ]=1로 설정

  데이터가 많아지면 메모리, 시간, 공간 낭비가 큰 방식

- 노드가 n개이고, edge 정보가 주어졌을때 인접 행렬로 그래프 구현하기

graph = [[0 for _ in range(n)] for _ in range(n)]

for [i, j] in edges:
	graph[i-1][j-1]=1
  	graph[j-1][i-1]=1	#무향 그래프일때

 

- 그래프 구현 2 : 인접 리스트 (리스트 배열)

  list를 원소로 하는 배열 생성 → i와 인접한 노드를 i번째 list에 저장

graph = [[] for _ in range(n)]

for [i,j] in edges:
	graph[i-1].append(j-1)
  	graph[j-1].append(i-1)		#무향 그래프일때

 

 

- 연습 문제 : 연결된 영역의 개수

- 시작점 1을 기준으로 DFS 실행, DFS로 방문한 = 1과 연결된 노드를 ch list에 저장

- graph[v]에 있는, v의 인접 노드 중에서 방문하지 않은 노드에 대해 DFS

def DFS(v, graph, ch, n):
    for j in graph[v]:
        if ch[j]==0:
            ch[j]=1
            DFS(j, graph, ch, n)    


def solution(n, edges):
	#인접 리스트로 그래프 구현
    graph = [[] for _ in range(n)]
    for [i, j] in edges:
        graph[i-1].append(j-1)
        graph[j-1].append(i-1)

    ch=[0 for _ in range(n)]
    ch[0]=1
    for i in graph[0]:
        ch[i]=1
        DFS(i, graph, ch, n)
    return n-sum(ch)