#2-3 Python 코딩테스트 그리디 알고리즘 , DFS & BFS

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2 

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 

이 포스트는 위의 영상을 보고 제가 필요하다고 생각된 부분을 정리한 포스팅입니다.

 

그리디 알고리즘 : 현재 상태에서 지금 당장 좋은 것만 고르는 방법-> 이 방법을 이용했을 때 최적의 해를 구할 수 있는지 검토하는 것이 필요함.

 

스택 , 큐 :
- 스택은 선입 후출 형태 list를 그대로 사용한다. append, pop을 활용.

- 큐는 선입선출 형태 

from collections import deque

queue = deque()
queue.append(3)
queue.popleft()

# 시간 복잡도가 상수.

재귀 함수 : 자기 자신을 그대로 호출.

- 팩토리얼 메서드

def factorial_recursive(n):
    if n <=1: # n이 1 이하인 경우 1을 반환
    	return 1
    # n! = n * (n-1)!
    return n * factorial_recursive(n - 1)

- 최대 공약수 (유클리드 호제법)

- 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지가 R 일 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같음.

def gcd(a, b):
    if a % b ==0:
    	return b
    else :
    	return gcd(b, a % b)

 

- DFS (Depth-First-Search)

깊이 우선 탐색 -> 깊은 부분을 우선적으로 탐색하는 알고리즘

스택 or 재귀 함수 이용

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있으면 그 노드를 스택에 넣고 방문 처리

   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번 과정 수행할 수 없을 때까지 반복.

 

dfs 그래프 예시

위 그래프를 dfs 기준으로 반복한다 했을 때의 코드

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end=' ')
    # 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)


# 각 노드의 연결된 정보 표현
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
# 노드 방문된 정보 표현
visited = [False] * 9

# dfs 함수 호출
dfs(graph, 1, visited)

 

- BFS (Breadth-First Search)

너비 우선 탐색 - 가까운 노드부터 우선적으로 탐색하는 알고리즘

큐 자료구조 사용

 

1. 탐색 시작 노드를 큐에 삽입 후 방문 처리

2. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위한 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드 방문처리
    visited[start] = True
    while(queue):
    	# 큐에서 하나씩 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 방문 하지 않은 인접한 원소들을 큐에 삽입
        for i in graph([v]):
            queue.append(i)
            visited(i) = True
             
    


# 각 노드의 연결된 정보 표현
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
# 노드 방문된 정보 표현
visited = [False] * 9

# dfs 함수 호출
dfs(graph, 1, visited)

음료수 얼려 먹기

- 내가 작성한 코드

# 음료수 얼려먹기 dfs
N , M = map(int,input().split())
ice = [[0]*M for _ in range(N)]
for i in range(N):
    ice[i] = list(map(int,input()))
visited = [[False]*M for _ in range(N)]
# L R U D
move = [(0,-1),(0,1),(-1,0),(1,0)]
result = 0
def dfs(ice,visited,x,y,move):
    visited[x][y]=True
    for mov in move:
        dx = x + mov[0]
        dy = y + mov[1]
        if dx > -1 and dx < N and dy > -1 and dy < M:
            if ice[dx][dy] == 0 and visited[dx][dy] == False:
                dfs(ice,visited,dx,dy,move)
for i in range(N):
    for j in range(M):
        if ice[i][j] == 0 and visited[i][j] == False:
            dfs(ice,visited,i,j,move)
            result +=1
print(result)

답안 예시

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >=m:
    	return False
    if graph[x][y] == 0:
    	graph[x][y] = 1
        dfs(x - 1, y)
        dfs(x, y -1 )
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False

n , m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            resultg +=1
print(result)

나는 변수를 덕지덕지 썼는데 답안 예시를 보게 되니 훨씬 깔끔하게 풀 수 있음을 알게 되었다.

 

미로 탈출

내가 쓴 코드

# 미로 탈출 bfs
from collections import deque
def bfs(x,y):
    queue = deque()
    queue.append((x,y,1))
    graph[x][y] = 0
    while queue:
        x, y, move = queue.popleft()
        if x == N-1 and y == M-1:
            return move
        if x - 1 > -1 : # move up
            if graph[x-1][y] !=0:
                graph[x-1][y] = 0
                queue.append((x-1,y,move+1))
        if x + 1 < N : # move down
            if graph[x+1][y] !=0:
                graph[x+1][y] = 0
                queue.append((x+1,y,move+1))
        if y - 1 > -1 : # move left
            if graph[x][y-1] !=0:
                graph[x][y-1] = 0
                queue.append((x,y-1,move+1))
        if y + 1 < M : # move right
            if graph[x][y+1] !=0:
                graph[x][y+1] = 0
                queue.append((x,y+1,move+1))
N, M = map(int,input().split())

graph = []

for i in range(N):
    graph.append(list(map(int,input())))
print(bfs(0,0))

답안 예시

from collections import deque
def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = x + dy[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    return graph[n - 1][m - 1]

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

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

print(bfs(0, 0))

 

나는 해당 노드가 0이 아닐 경우만 이동할 수 있고 해당 노드를 한번 밟으면 0으로 변경해서 다시 못 밟게 설정한 후,

move 값을 증가시켰는데

예시 코드처럼 해당 노드가 1 일 경우에 graph 값을 + 1 시켜주며 이것으로 최단 경로를 파악할 수 있다는 것을 알게 되었다.

예시 코드가 좀 더 직관적이고 이해하기 쉬운 것 같다.

 

 

DFS는 스택이나 재귀

BFS는 queue를 활용하면 쉽게 문제를 풀 수 있다.