[Python] 백준 알고리즘 graph : DFS,BFS + 문제풀이 1260, 11724, 10451, 2331, 2667, 4963, 7576, 2178, 2146
이번 한 주 동안은 DFS, BFS 를 간단하게 구현해보고
백준에서 알고리즘 문제를 풀어봤다!
우선, tree의 vertex, edge 정보를 담은 list를 만들고
vertexList = [0,1,2,3,4,5,6]
edgeList = [(0,1), (0,2), (1,0), (1,3), (2,0), (2,4), (2,5), (3,1), (4,2), (4,6), (5,2), (6,4)]
adjencyList = [[] for vertex in vertexList]
for edge in edgeList: #각각 vertex 0 ~ 6가 어떤 vertex와 edge를 가지고 있는지
adjencyList[edge[0]].append(edge[1])
1. BFS
# BFS
import queue
q=queue.Queue()
q.put(0)
visitedVertex = []
while q.qsize():
current = q.get()
for neighbor in adjencyList[current]:
if not neighbor in visitedVertex:
q.put(neighbor)
visitedVertex.append(current)
print(visitedVertex)
2. DFS
# DFS
stack = [0]
visitedVertex = []
while stack:
current = stack.pop()
for neighbor in adjencyList[current]:
if not neighbor in visitedVertex:
stack.append(neighbor)
visitedVertex.append(current)
print(visitedVertex)
3. boj
1260: BFS DFS : DFS와 BFS
# 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다
n, m, v = map(int, input().split())
edgeList = []
vertexList = []
for i in range(m):
temp = input() # 간선 정보
a,b = temp.split()
vertexList.append(int(a))
vertexList.append(int(b))
edgeList.append((int(a), int(b)))
edgeList.append((int(b), int(a)))
vertexList = list(set(vertexList))
adjencyList = [[] for i in range(1001)]
for edge in edgeList:
adjencyList[edge[0]].append(edge[1])
for adj in adjencyList:
if len(adj)>1:
adj.sort()
for adj in adjencyList:
if len(adj)>1:
adj.sort(reverse=True)
# DFS
stack = [v]
visitedVertex = []
while stack:
current = stack.pop()
for neighbor in adjencyList[current]:
if not neighbor in visitedVertex:
stack.append(neighbor)
visitedVertex.append(current)
if len(visitedVertex) == n:
break
print("DFS : ")
for visited in visitedVertex:
print(visited, end = ' ')
print()
# BFS
import queue
for adj in adjencyList:
if len(adj)>1:
adj.sort()
q=queue.Queue()
q.put(v)
visitedVertex = []
while True:
current = q.get()
for neighbor in adjencyList[current]:
if not neighbor in visitedVertex:
q.put(neighbor)
visitedVertex.append(current)
if len(visitedVertex) == n:
break
print("BFS: ")
for visited in visitedVertex:
print(visited, end = ' ')
print()
런타임 에러는 왜 나는걸까 ㅠㅠㅠ
# 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성
def count_cc(edgeL, vertexL, adjencyL, startpoint):
visitedVertex = []
stack = [startpoint]
while len(stack)>0:
current = stack.pop()
for neighbor in adjencyList[current]:
if not neighbor in visitedVertex:
stack.append(neighbor)
visitedVertex.append(current)
if len(visitedVertex) == n:
return 1
else:
for vertex in vertexL:
if vertex not in visitedVertex:
startpoint = vertex
break
return 1+count_cc(edgeL, vertexL, adjencyL, startpoint)
# 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
# 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
n, m = map(int, input().split())
edgeList = []
vertexList = []
for i in range(m):
temp = input() # 간선 정보
a,b = temp.split()
vertexList.append(int(a))
vertexList.append(int(b))
edgeList.append((int(a), int(b)))
edgeList.append((int(b), int(a)))
vertexList = list(set(vertexList))
adjencyList = [[] for i in range(1001)]
for edge in edgeList:
adjencyList[edge[0]].append(edge[1])
print(count_cc(edgeList, vertexList, adjencyList, vertexList[0]))
처음에는 이렇게 풀었는데 자꾸 recursion error가 뜨고, 백준에서도 시간 초과가 뜨더라 ㅠㅠ
근데 그럴만해,,, 재귀함수 안에 while을 넣었으니 시간복잡도가 거진 O(N^2) 겠지 모,,,
n, m = map(int, input().split())
edgeList = []
vertexList = []
for i in range(m):
temp = input() # 간선 정보
a,b = temp.split()
vertexList.append(int(a))
vertexList.append(int(b))
edgeList.append((int(a), int(b)))
edgeList.append((int(b), int(a)))
vertexList = list(set(vertexList))
adjencyList = [[] for i in range(1001)]
for edge in edgeList:
adjencyList[edge[0]].append(edge[1])
cc = 0
stack = [vertexList[0]]
visitedVertex = []
while len(visitedVertex) != n:
while stack:
current = stack.pop()
for neighbor in adjencyList[current]:
if not neighbor in visitedVertex:
stack.append(neighbor)
visitedVertex.append(current)
if len(visitedVertex) == n:
break
cc += 1
for vertex in vertexList:
if vertex not in visitedVertex:
stack = [vertex]
print(cc)
recursion 안쓴 버전도 만들었는데 자꾸 시간 초과가 뜨더라구요 ㅠㅠㅠ 엉엉
그래서 이렇게 두 문제를 풀고 나서, 다른 분들의 코드를 보니까
내가 엄청 매우 굉장히 무겁게 문제를 풀고 있다는 걸 알아냈다,,,,
다른 분들의 코드는 진짜 가볍더라구용,,,
# 출처 : https://velog.io/@devjuun_s/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C%EC%9D%98-%EA%B0%9C%EC%88%98-%EB%B0%B1%EC%A4%80-11724%EB%B2%88python
import sys
sys.setrecursionlimit(10000)
def dfs(v):
visited[v] = True
for e in adj[v]:
if not visited[e]:
dfs(e)
N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
count = 0
for _ in range(M):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
for j in range(1, N + 1):
if not visited[j]:
dfs(j)
count += 1
print(count)
10451: 순열 사이클 이 문제는 문제 이해가 너무 안되도라,,
순열을 배열로 나타낸다는 말이 처음에 이해가 안되었지만 무난하게 풀었당
def dfs(v):
visited[v] = True
for e in adj[v]:
if not visited[e]:
dfs(e)
result = []
for i in range(2): #t번 반복
cc = 0
n = int(input()) # 순열의 개수
adj = [[] for _ in range(n+1)]
permut = [ _ for _ in map(int, input().split())]
for i in range(n):
adj[i+1].append(permut[i])
visited = [False] * (n+1)
for j in range(1, n+1):
if not visited[j]:
dfs(j)
cc += 1
result.append(cc)
#결과 출력
for re in result:
print(re)
def calcul(a, b):
a = str(a)
b = int(b)
total = 0
for n in a:
total += (pow(int(n),b))
return total
a, b = input().split()
num_list = [int(a)]
while True:
result = calcul(a,b)
if result in num_list:
break
num_list.append(result)
a = result
print(num_list.index(result))
마찬가지로 처음에는 조금 헷갈렸지만, adjencyMatrix를 생각하니까 좀 이해가 되더라.
그리고 아래 두 문제들도 비슷한 개념이도라구
def count_house(houses,i,j, visited): # i,j는 index
'''
왼쪽, 위 에서부터 시작하므로, 이동은 무조건 오른쪽, 왼쪽, 아래
그러므로 아래로 더 못내려 가거나, 오른쪽으로 더 못가는 경우만 생각하기
'''
result = 0
visited[i][j] = True
if houses[i][j]==1:
result+=1
else:
return result
if i == n-1:
if j==n-1: #오른쪽, 아래로 못갈 때 (더이상 이동 x)
return result
else: # 오른쪽으로 못갈 때
return result + count_house(houses, i, j+1, visited)
else:
return result + count_house(houses, i+1, j, visited) + count_house(houses, i, j+1, visited)
n = int(input())
houses = []
for i in range(n):
houses.append([ _ for _ in input()])
for j in range(n):
houses[i][j] = int(houses[i][j])
visited = [[False for _ in range(n)] for _ in range(n)]
count = [] # 각 단지의 house 개수
for k in range(n):
for m in range(n):
if not visited[k][m]:
count.append(count_house(houses, k, m, visited))
result = []
for c in count:
if c!=0:
result.append(c)
result.sort()
for re in result:
print(re)
이 문제는 dfs 랑 연결 요소가 섞인 문제당
즉, 상하좌우의 방향으로 1-1 끼리 Edge들이 연결되어 있는 트리 로 접근했다.
4963: 섬의 개수도 같은 유형이당
+
난 런타임 에러가 정말 싫엉 히히
자꾸 recursion limit 걸리면
import sys
sys.setrecursionlimit(2000)
이렇게 limit를 풀어주세용
7576: 토마토 문제는 저번에 도전했다가 결국 그래도 뒀던 것,,,
오늘 풀었는데 아직도 너무 어렵다 또르르
# 숫자를 입력받기
m, n = map(int, input().split())
# 초기 상태
tomatoes = []
green = 0
red = 0
day = 0
for i in range(n):
tomatoes.append(input().split())
for j in range(m):
tomatoes[i][j] = int(tomatoes[i][j])
if tomatoes[i][j] == 0:
green+=1
elif tomatoes[i][j] == 1:
red+=1
reds.append([i,j])
total = green+red
checked = [[False for _ in range(m)]for _ in range(n)]
reds = []
def ripen(tomatoes, i, j, checked):
'''
input: i와 j는 시작 index(익은 부분부터 시작)
output: 다익는데 걸리는 날짜
'''
print(str(i)+"&"+str(j)+"th")
if i<n and j<m and tomatoes[i][j] != -1 and checked[i][j] == False:
checked[i][j] = True
red +=1
if i == 0:
if j == 0:
return 1+ripen(tomatoes, i, j+1, checked)+ripen(tomatoes, i+1, j, checked)
elif j == n-1:
return 1+ripen(tomatoes, i, j-1, checked)+ripen(tomatoes, i+1, j, checked)
else:
return 1+ripen(tomatoes, i, j+1, checked)+ripen(tomatoes, i, j-1, checked)+ripen(tomatoes, i+1, j, checked)
elif i == m-1:
if j == 0:
return 1+ripen(tomatoes, i, j+1, checked)+ripen(tomatoes, i-1, j, checked)
elif j == n-1:
return 1+ripen(tomatoes, i, j-1, checked)+ripen(tomatoes, i-1, j, checked)
else:
return 1+ripen(tomatoes, i, j+1, checked)+ripen(tomatoes, i, j-1, checked)+ripen(tomatoes, i-1, j, checked)
else:
return 1+ripen(tomatoes, i, j+1, checked)+ripen(tomatoes, i+1, j, checked)+ripen(tomatoes, i-1, j, checked) + ripen(tomatoes, i, j-1, checked)
for i in range(len(reds)):
a,b = reds[i]
day = ripen(tomatoes, a, b, checked)
if red == total: print(day)
elif green == total: print(0)
else: print(-1)
처음엔 이렇게 작성했는데 음,,, 어 음,,,
이 토마토 문제는 결국 다른 분의 코드를 참고했다!
우선, 한 방향으로 쭉 익는 것이 아니라 익은 토마토 주변부가 익기 시작하기 때문에 BFS로만 풀어야 하는 문제라는 것.
그리고 시간을 줄이기 위해 input()대신 sys.stdin.readline를 이용한 것
좌우상하를 나타내기 위해 dx,dy를 이용한 것 등등 !
엄청 탄탄하게 짜신 분들이 많아서 부러웠다,, ㅋㅋ쿠ㅜㅜㅠㅠㅜ
2178: 미로찾기 도 토마토와 마찬가지로 BFS 문제이당
다른 데에서 참고했는데 확실히 dx, dy랑 이를 이용한 for문을 쓰니까 코드가 어엄청 간단해졌다…!
# https://hongku.tistory.com/276
n, m = map(int, input().split())
miro = []
for i in range(n):
miro.append([ _ for _ in input()])
for j in range(m):
miro[i][j] = int(miro[i][j])
visited = [[ False for _ in range(m)] for _ in range(n)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
# BFS
ary = []
ary.append((0,0))
visited[0][0] = 1
while ary:
x, y = ary.pop(0)
if x == n-1 and y == m-1:
print(visited[x][y])
else:
for i in range(4): # 각각 위, 아래, 왼쪽, 오른쪽을 나타냄
ax = x + dx[i]
ay = y + dy[i]
if ax>=0 and ax<n and ay>=0 and ay<m:
if visited[ax][ay]== 0 and miro[ax][ay] == 1:
#print(str(ax) + " and " + str(ay) + " ; " + str(visited[ax][ay]))
visited[ax][ay] = visited[x][y] + 1
ary.append((ax, ay))
2146: 다리만들기는 너무 어려웠던 게,,, 출발한 섬을 도착지로 오해햐는 경우도 다뤄야 했기 때문이다
사실 처음에는 이렇게 했는데
n = int(input())
ls = [] # 육지, 바다의 정보 저장
for i in range(n):
ls.append(input().split())
visited = [[ 0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if ls[i][j] == '1':
visited[i][j] = -1 # 섬이 있는 곳 체크
dx = [0,0,1,-1]
dy = [1,-1,0,0]
start = []
for x in range(n):
for y in range(m):
for i in range(4):
ax = x + dx[i]
ay = y + dy[i]
if ax>=0 and ay>=0 and ls[x][y] == '1' and ls[ax][ay] == '0':
start.append((ax,ay))
steps = []
for s in range(len(start)):
startpoint = [start[s]]
temp = copy.deepcopy(visited) # deep copy
while startpoint:
#print(startpoint)
a,b = startpoint.pop(0)
#if ls[a][b] == '1':
# print(temp[a][b])
# break
#print('this is : '+ str(a) +" & "+str(b))
for i in range(4):
ax = a + dx[i]
ay = b + dy[i]
if ax>=0 and ax<n and ay>=0 and ay<n:
if temp[ax][ay] == 0 and ls[ax][ay] == '0':
temp[ax][ay] = temp[a][b] + 1
startpoint.append((ax,ay))
elif ls[ax][ay] == '1': # 육지에 도착했을 때
#print("reach the land!")
print(str(a)+' & '+ str(b))
print(str(ax)+' & '+ str(ay))
steps.append(temp[a][b])
break
print(min(steps))
이렇게 하니까 출발한 곳으로 도착하는 상황 발생함,,
그래서 dfs를 이용하여 같은 섬끼리는 구분하게끔 코드를 수정하였당 즉 grouping을 해주어야 겠다고 생각했다.
근데 백준 선생님이 말씀하시길 한 문제에 2시간 이상 쏟지 말라고,,, 그래서 이번에도 다른 분들의 코드를 살펴봤당 ㅠㅠ
근데 이번 월요일부터 오늘까지(금요일) 내내 dfs, bfs 같은 트리 문제를 풀면서 느낀 점이
내가 tree의 개념을 아직 잘 이해 못한건가 ..? 싶었다
왜냐하면 풀면 풀수록 어려운 기분이 들어서,, 아니 다들 척척 풀던데 왜 나만 못풀어 ㅠㅠㅠ
그래도 이제는 어떤 문제에서는 dfs, 어떤 문제에서는 bfs 로 풀 수 있는 건지 대충 보이기는 한당