[알고리즘] DFS / BFS + 백준 10828 10845 17478 1388 2606 1260 1325 2138

선행 개념

스택, 큐, 재귀 개념을 먼저 공부하고 들어가자.

 

Stack

스택은 박스 쌓기로 생각하면 편하다.

나중에 쌓인 것이 가장 먼저 들릴 수 있는 것처럼, 이러한 구조를 LIFO(Last In First Out)라 한다.

파이썬에서는 리스트로 스택을 구현할 수 있다.

stack = []

stack.append(1)	# [1]
stack.append(2)	# [1, 2]
stack.append(3)	# [1, 2, 3]
stack.pop()	# [1, 2]
stack.append(4)	# [1, 2, 4]

 

pop() 메소드는 가장 뒤의 데이터를 제거하고, append는 가장 뒤에 데이터를 삽입한다.

 

백준 10828 스택

import sys

n = int(input())
stack = []
cmd = [sys.stdin.readline().rstrip() for _ in range(n)]
    
for x in cmd:    
    if 'push' in x:
        x = x.replace('push ', '')
        num = int(x)
        stack.append(num)
    elif x == 'pop':
        if len(stack) >= 1:
            print(stack.pop())
        else:
            print(-1)
    elif x == 'size':
        print(len(stack))
    elif x == 'empty':
        if len(stack) == 0:
            print(1)
        else:
            print(0)
    elif x == 'top':
        if len(stack) >= 1:
            print(stack[-1])
        else:
            print(-1)

 

Queue

큐는 줄을 서는 것을 생각하면 된다.

나중에 온 사람이 가장 마지막에 들어가게 되고, 먼저 온 사람이 가장 먼저 들어가게 되는 FIFO(First In First Out) 구조이다.

파이썬의 collections 모듈에서 제공하는 deque로 큐를 구현할 수 있다.

 

from collections import deque

q = deque()

q.append(1)	# deque([1])
q.append(2)	# deque([1, 2])
q.append(3)	# deque([1, 2, 3])
q.popleft()	# deque([2, 3])
q.append(4)	# deque([2, 3, 4])

deque 객체를 list() 메소드를 이용해 리스트로 변경할 수도 있다.

 

 

백준 10845 큐

import sys
from collections import deque

n = int(input())
q = deque()
cmd = [sys.stdin.readline().rstrip() for _ in range(n)]

for x in cmd:
    if 'push' in x:
        num = int(x.replace('push ', ''))
        q.append(num)
    elif x == 'pop':
        if len(q) != 0:
            print(q.popleft())
        else:
            print(-1)
    elif x == 'size':
        print(len(q))
    elif x == 'empty':
        if len(q) == 0:
            print(1)
        else:
            print(0)
    elif x == 'front':
        if len(q) > 0:
            print(q[0])
        else:
            print(-1)
    elif x == 'back':
        if len(q) > 0:
            print(q[-1])
        else:
            print(-1)

 

 

Recursive function

재귀 함수는 말 그대로 자기 자신을 호출하는 함수다.

def recursive_function():
	print('난 재귀 함수야')
    recursive_function()
    
>>> 
난 재귀 함수야
난 재귀 함수야
난 재귀 함수야
난 재귀 함수야
난 재귀 함수야
난 재귀 함수야
...

재귀 함수의 종료 조건을 명시해주지 않으면 무한 호출에 빠지므로, 꼭 종료 조건을 명시해주어야 한다!

 

 

백준 17478 재귀함수가 뭔가요?

 

n = int(input())
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")

def recursive_function(num):
    if num == 0:
        return
    if num > 0:
        print("_" * 4 * (n-num) + '"재귀함수가 뭔가요?"')
        print("_" * 4 * (n-num) + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
        print("_" * 4 * (n-num) + '마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.') 
        print("_" * 4 * (n-num) + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
    recursive_function(num-1)
        
recursive_function(n)
print("_" * 4 * n + '"재귀함수가 뭔가요?"')
print("_" * 4 * n + '"재귀함수는 자기 자신을 호출하는 함수라네"')
for i in range(n, -1, -1):
    print("_" * 4 * i + "라고 답변하였지.")

일단 정답은 맞는 코든데... 뭔가 더 좋은 방법이 있을거 같지만 DFS/BFS 먼저 공부해보고 담에 돌아와서 수정하는걸로!!

 

DFS/BFS

 

DFS(Depth-First Search)

 그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘.

여기서 말하는 그래프란? 노드와 간선으로 표현되는 아래 그림과 같은 것이다.

 

이러한 그래프는 파이썬으로 두가지 방식을 통해 나타낼 수 있다.

- 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현

- 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현

 

 

인접 행렬(Adjacency Matrix)

 연결이 되어있지 않은 노드끼리는 무한의 비용이라 가정하고, 그래프를 인접 행렬 방식으로 코드를 작성해보자.

INF = 999999
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]

 

인접 리스트(Adjacency List)

흔히 linked list를 이용해 구현하는데, 파이썬은 그냥 리스트 쓰면 된다.

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

graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))
graph[2].append((0,5))

print(graph)

>>> [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

인접 행렬 방식은 모든 관계를 저장 / 인접 리스트 방식은 연결 정보만을 저장 -> 메모리 효율 ↑ 연결 정보 얻는 속도 ↓

특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 메모리 효율이 더 좋다.

DFS = 깊이 우선 탐색 = 특정 상황에서 최대한 깊이 들어가 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘

 

1) 탐색 시작 노드를 스택에 삽입 후 방문 처리

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

3) 반복

 

뭔 소린가 싶다.... 난 바보다...... 코드로 자세히 알아보자

 

def dfs(graph, v, visited):
	visited[v] = True
	print(v, end = ' ')
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

 뭔 소린가 싶은데... 코드를 하나씩 해석해보자.

v는 현재 노드고, 방문했으니까 방문 노드를 방문 처리 -> True

그리고 graph의 현재 노드와 연결된 다른 노드들을 재귀적으로 방문한다.

 

 

BFS(Breadth First Search)

 너비 우선 탐색 - 가까운 노드부터 탐색하는 방식

동작 방식은 다음과 같다.

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

2) 큐에서 노드를 pop, pop된 노드의 인접 노드중 방문하지 않은 노드를 모두 큐에 삽입

3) 반복

 

from collections import deque

def bfs(graph, start, visited):
	q = deque([start])
    visited[start] = True	#현재 노드 방문처리
    while q:
    	v = q.popleft()
        print(v, end = ' ')
        for i in graph[v]:
        	if not visited[i]:
            	q.append(i)
                visited[i] = True

 

 

백준 1388 바닥 장식

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

graph = []

for i in range(n):
    s = input()
    graph.append(list(s))
    
def dfs_h(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    
    if graph[x][y] == '-':
        graph[x][y] = 1
        dfs_h(x, y+1)
        dfs_h(x, y-1)
        return True
    
def dfs_v(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if graph[x][y] == '|':
        graph[x][y] = 1
        dfs_v(x-1, y)
        dfs_v(x+1, y)
        return True
    return False


a1 = 0
a2 = 0
for i in range(n):
    for j in range(m):
        if dfs_h(i, j) == True:
            a1 += 1
        if dfs_v(i, j) == True:
            a2 += 1
print(a1 + a2)

DFS를 사용하여 풀어봤다. -인 경우와 |인 경우를 나누어 두 dfs 함수를 구현하여 풀었는데

맞는 건지는 모르겠지만 쨌든 통과는 했다.

 

 

백준 2606 바이러스

 

from collections import deque

c = int(input())
n = int(input())
tmp = []
for i in range(n):
    k = list(map(int, input().split()))
    tmp.append(k)
    tmp.append(k[::-1])
    
tmp = sorted(tmp, key = lambda x:x[0])

graph = [[]]

for i in range(1, c+1):
    temp = []
    for x in tmp:
        if x[0] == i:
            temp.append(x[1])
    graph.append(temp)
def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
    print(sum(visited)-1)

visited = [False] * (c+1)

bfs(graph, 1, visited)

 

백준 1260 DFS와 BFS

from collections import deque

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

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    while q:
        v = q.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True

tmp = []
for _ in range(m):
    k = list(map(int, input().split()))
    tmp.append(k)
    tmp.append(k[::-1])

graph = [[]]*(n+1)

tmp = sorted(tmp, key = lambda y:(y[0], y[1]))
for i in range(1, n+1):
    temp = []
    for x in tmp:
        if x[0] == i:
            temp.append(x[1])        
    graph[i] = temp
    
visited1 = [False] * (n+1)
visited2 = [False] * (n+1)
dfs(graph, l, visited1)
print("")
bfs(graph, l, visited2)

 

 

백준 1325 효율적인 해킹

 

첨에 BFS 하면 엄청 편하겠다 싶었는데 시간 초과ㅏㅏㅏㅏㅏㅏㅏㅏㅏ 

from collections import deque
import sys
n, m = map(int, input().split())

graph = [[]]*(n+1)
tmp = [0] * m
for i in range(m):
    temp = list(map(int, sys.stdin.readline().rstrip().split()))
    tmp[i] = temp[::-1]
    
tmp = sorted(tmp, key = lambda x: x[0])

for i in range(1, n+1):
    temp = []
    for x in tmp:
        if x[0] == i:
            temp.append(x[1])
    graph[i] = temp
    
def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    cnt = 0
    while q:
        v = q.popleft()
        cnt += 1
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
    return cnt

cntlist = [0]*(n+1)

for x in range(1, n+1):
    visited = [False] * (n+1)
    cntlist[x] = bfs(graph, x, visited)
    
for i in range(1, n+1):
    if cntlist[i] == max(cntlist):
        print(i, end = ' ')

이건 시간 초과되어버린 내 코드다... 어떻게 시간초과를 해결할 수 있을까.........

 

from collections import deque
n, m = map(int, input().split())

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

for _ in range(m):
    i, j = map(int, input().split())
    graph[j].append(i)
    
def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    cnt = 1
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
                cnt += 1
    return cnt

max_cnt = 0
result = []
for x in range(1, n+1):
    visited = [False] * (n+1)
    cnt = bfs(graph, x, visited)
    if cnt > max_cnt:
        max_cnt = cnt
    result.append([x, cnt])

for idx, cnt in result:
    if cnt == max_cnt:
        print(idx, end = ' ')

그래프 입력받는 과정을 좀 간소화했더니 풀렸다. 허무ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ해

 

백준 2138 전구와 스위치 - 복습문제

 

n = int(input())
current = input()
want = input()

change = {'00': '11', '01': '10', '10': '01', '11': '00', '000': '111', '001': '110', '010': '101', '011': '100', '100': '011', '101': '010', '110': '001', '111': '000'}
tmp = current
tmp2 = current
cnt = 0
cnt2 = 1

# 0번스위치 안눌러
for s in range(1,n-1):
    if tmp[s-1] != want[s-1]:
        cnt += 1
        tmp = tmp.replace(tmp[s-1:s+2], change[tmp[s-1:s+2]])
        
if tmp[n-1] != want[n-1]:
    cnt += 1
    tmp = tmp.replace(tmp[n-2:], change[tmp[n-2:]])

if tmp != want:
    cnt = 0

# 0번을 누르고 시작

tmp2 = tmp2.replace(tmp2[:2], change[tmp2[:2]])
for s in range(1,n-1):
    if tmp2[s-1] != want[s-1]:
        cnt2 += 1
        tmp2 = tmp2.replace(tmp2[s-1:s+2], change[tmp2[s-1:s+2]])
        
if tmp[n-1] != want[n-1]:
    cnt2 += 1
    tmp2 = tmp2.replace(tmp2[n-2:], change[tmp2[n-2:]])

    
    
if tmp != want and tmp2 != want:
    print(-1)

else:
    if tmp == want and tmp2 == want:
        print(min(cnt, cnt2))
    else:
        if tmp == want:
            print(cnt)
        else:
            print(cnt2)

시반 초과가 나왔다.............................................. 진짜 열심히 풀었는데......................................

근데 코드도 다시 보니까 틀렸더라 ㅋㅋ

ㅋㅋ

ㅋㅋ

...

 

그래서 수정 열심히 해서 코드 다시 짰다. 성공~~~~~~~~~~~~~ sys 사용해서 조금이라도 빠르게 하려고 노력함

import sys
n = int(input())
current = sys.stdin.readline().rstrip()
want = sys.stdin.readline().rstrip()

change = {'00': '11', '01': '10', '10': '01', '11': '00', '000': '111', '001': '110', '010': '101', '011': '100', '100': '011', '101': '010', '110': '001', '111': '000'}
tmp = current
tmp2 = current
cnt = 0
cnt2 = 1

# 0번스위치 안눌러
for s in range(1,n-1):
    if tmp[s-1] != want[s-1]:
        cnt += 1
        tmp = tmp[:s-1] + change[tmp[s-1:s+2]] + tmp[s+2:]
        
if tmp[n-1] != want[n-1]:
    cnt += 1
    tmp = tmp[:n-2] + change[tmp[n-2:]]
    
if tmp != want:
    cnt = 0

# 0번을 누르고 시작

tmp2 = change[tmp2[:2]] + tmp2[2:]

for s in range(1,n-1):
    if tmp2[s-1] != want[s-1]:
        cnt2 += 1
        tmp2 = tmp2[:s-1] + change[tmp2[s-1:s+2]] + tmp2[s+2:]        
        
if tmp2[n-1] != want[n-1]:
    cnt2 += 1
    tmp2 = tmp2[:n-2] + change[tmp2[n-2:]]

    
    
if tmp != want and tmp2 != want:
    print(-1)

else:
    if tmp == want and tmp2 == want:
        print(min(cnt, cnt2))
    else:
        if tmp == want:
            print(cnt)
        else:
            print(cnt2)