BFS_그래프_인접구역탐색
#1. 시작점을 큐에다 삽입한다.
#2. 시작점을 방문한다(True 변경)
# BFS 시작
#3. 큐에서 하나를 뺀다. 얘가 우리의 현재 위치이다.
#4. 인접한 모든 정점에게 방문했는지 물어보고 방문을 하지 않았으면 True 변경
#5. 큐에 삽입
#6. 모두 완료시 3으로 돌아감
from collections import deque
def BFS(start) :
visited[start] = True #시작점 방문 완료
dq.append(start) #처음 시작점 큐에 삽입
while dq : #큐가 텅 비기 전까지 반복
node = dq.popleft() #큐에 맨앞 POP
print(node, end=" ")
for next in graph[node] : #node와 연결된 다음 노드 큐에 삽입
if visited[next] is False : #방문하지 않았다면
visited[next] = True #방문처리
dq.append(next) #큐에 넣기
vertex_n, edge_n = 9, 12
graph = [[] for _ in range(vertex_n+1)]
visited = [False] * (vertex_n+1)
dq = deque()
input_data = [[1, 2],
[1, 3],
[2, 3],
[2, 4],
[2, 6],
[3, 7],
[4, 5],
[4, 7],
[4, 8],
[5, 6],
[7, 8],
[8, 9]]
for data in input_data :
vertex, edge = data
graph[vertex].append(edge)
graph[edge].append(vertex)
print(graph)
#graph[1]부터 탐색 시작
BFS(1)
#입력
# 9 12
# 1 2
# 1 3
# 2 3
# 2 4
# 2 6
# 3 7
# 4 5
# 4 7
# 4 8
# 5 6
# 7 8
# 8 9
BFS_이차원리스트_떨어져있는구역방문_8방향
import sys
from collections import deque
def BFS(start_x, start_y, map_data, count, n) :
dx = [-1, -1, 0, 1, 1, 1, 0, -1] #top 0, top-right 1, right 2, right-bottom 3, bottom 4, botton-left 5, left 6, left-top 7
dy = [0, 1, 1, 1, 0, -1, -1, -1]
dq = deque() #BFS를 위한 큐 생성
count += 1
dq.append((start_x, start_y)) #1. 큐에 시작점 추가
map_data[start_x][start_y] = 0 #2. 큐에 넣은 시작점은 방문처리
while dq :
now_idx = dq.popleft() #현재 방문 노드
for d in range(8) : #8방향 이동(top 0, top-right 1, right 2, right-bottom 3, bottom 4, botton-left 5, left 6, left-top 7)
next_x = now_idx[0] + dx[d] #큐에 들어간 좌표 중 연결된 다음 x좌표[0]
next_y = now_idx[1] + dy[d] #큐에 들어간 좌표 중 연결된 다음 y좌표[1]
#x좌표 내 and y좌표 내에서 이동 and 인접한 다음 방문할 곳이 길(1)인 경우 이동
if 0 <= next_x <= (n-1) and 0 <= next_y <= (n-1) and map_data[next_x][next_y] == 1:
count += 1
map_data[next_x][next_y] = 0 #방문한 곳은 벽(0)처리
dq.append((next_x, next_y))
return count
def solution() :
n = 7
result = []
map_data = [[0, 1, 1, 0, 1, 0, 0],
[0, 1, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0, 0]]
#완전 탐색 하면서 1 있는 곳은 BFS 시작
for i in range(n) :
for j in range(n) :
if map_data[i][j] == 1 :
count = 0
count = BFS(i, j, map_data, count, n)
result.append(count)
print(len(result))
solution()
#입력
# 7
# 0 1 1 0 1 0 0
# 0 1 1 0 1 0 1
# 1 1 1 0 1 0 1
# 0 0 0 0 1 1 1
# 0 1 0 0 0 0 0
# 0 1 1 1 1 1 0
# 0 1 1 1 0 0 0
#=> 결과 3
#입력
# 7
# 1 1 0 0 0 1 0
# 0 1 1 0 1 1 0
# 0 1 0 0 0 0 0
# 0 0 0 1 0 1 1
# 1 1 0 1 1 0 0
# 1 0 0 0 1 0 0
# 1 0 1 0 1 0 0
#=> 결과 5
BFS_이차원리스트_떨어져있는구역방문
import sys
from collections import deque
def BFS(start_x, start_y, map_data, count, n) :
dx = [-1, 0, 1, 0] #top 0, right 1, bottom 2, light 3
dy = [0, 1, 0, -1]
dq = deque() #BFS를 위한 큐 생성
count += 1
dq.append((start_x, start_y)) #1. 큐에 시작점 추가
map_data[start_x][start_y] = 0 #2. 큐에 넣은 시작점은 방문처리
while dq :
now_idx = dq.popleft() #현재 방문 노드
for d in range(4) : #4방향 이동(top-> right-> bottom-> light)
next_x = now_idx[0] + dx[d] #큐에 들어간 좌표 중 연결된 다음 x좌표[0]
next_y = now_idx[1] + dy[d] #큐에 들어간 좌표 중 연결된 다음 y좌표[1]
#x좌표 내 and y좌표 내에서 이동 and 인접한 다음 방문할 곳이 길(1)인 경우 이동
if 0 <= next_x <= (n-1) and 0 <= next_y <= (n-1) and map_data[next_x][next_y] == 1:
count += 1
map_data[next_x][next_y] = 0 #방문한 곳은 벽(0)처리
dq.append((next_x, next_y))
return count
def solution() :
n = 7
map_data = [[0, 1, 1, 0, 1, 0, 0],
[0, 1, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0, 0]]
result = []
#완전 탐색 하면서 1 있는 곳은 DFS 시작
for i in range(n) :
for j in range(n) :
if map_data[i][j] == 1 :
count = 0
count = BFS(i, j, map_data, count, n)
result.append(count)
print(result)
solution()
#입력
# 7
# 0110100
# 0110101
# 1110101
# 0000111
# 0100000
# 0111110
# 0111000
BFS_이차원리스트_미로찾기
from collections import deque
def BFS(start_x, start_y, map_data, row, colum) :
dx = [-1, 0, 1, 0] #top 0, right 1, bottom 2, light 3
dy = [0, 1, 0, -1]
dq = deque() #BFS를 위한 큐 생성
distance_list = [[0] * colum for _ in range(row)] #거리 저장 리스트
dq.append((start_x, start_y)) #1. 큐에 시작점 추가
map_data[start_x][start_y] = 0 #2. 큐에 넣은 시작점은 방문처리
while dq :
now_idx = dq.popleft() #현재 방문 노드
for d in range(4) : #4방향 이동(top-> right-> bottom-> light)
next_x = now_idx[0] + dx[d] #큐에 들어간 좌표 중 연결된 다음 x좌표[0]
next_y = now_idx[1] + dy[d] #큐에 들어간 좌표 중 연결된 다음 y좌표[1]
#x좌표 내 and y좌표 내에서 이동 and 인접한 다음 방문할 곳이 길(1)인 경우 이동
if 0 <= next_x <= (row-1) and 0 <= next_y <= (colum-1) and map_data[next_x][next_y] == 1:
map_data[next_x][next_y] = 0 #방문한 곳은 벽(0)처리
distance_list[next_x][next_y] = distance_list[now_idx[0]][now_idx[1]] + 1 #현재값의 거리에 + 1
dq.append((next_x, next_y))
print(distance_list)
return distance_list
def solution(map_data):
answer = 0
row = len(map_data)
colum = len(map_data[0])
distance_map = BFS(0, 0, map_data, row, colum)
if distance_map[row-1][colum-1] != 0 :
answer = distance_map[row-1][colum-1] + 1
else :
answer = -1
print(answer)
return answer
#0은 벽 1은 길
map_data = [[1,0,1,1,1],
[1,0,1,0,1],
[1,0,1,1,1],
[1,1,1,0,1],
[0,0,0,0,1]]
solution(map_data)
BFS_이차원리스트_여러시작점
# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
from collections import deque
def BFS(n, position) :
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
visited = [[False] * (n) for _ in range(n)]
distance = [[0] * (n) for _ in range(n)]
dq = deque(position) #1 좌표 큐에 넣기
#다수의 시작 점 방문 처리
for x, y in dq :
visited[x][y] = True
max_cnt = 0
while dq : #dq가 빌때까지
now_x, now_y = dq.popleft()
for d in range(4) :
next_x = now_x + dx[d]
next_y = now_y + dy[d]
if 0 <= next_x < n and 0 <= next_y < n and visited[next_x][next_y] is False :
dq.append((next_x, next_y))
distance[next_x][next_y] = distance[now_x][now_y] + 1
if max_cnt < distance[next_x][next_y] :
max_cnt = distance[next_x][next_y]
visited[next_x][next_y] = True
return max_cnt
def solution(n, garden):
answer = 0
position = []
for i in range(n) :
for j in range(n) :
if garden[i][j] == 1 :
position.append((i, j))
return BFS(n, position)
# n1 = 3
# garden1 = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
# ret1 = solution(n1, garden1)
# n2 = 2
# garden2 = [[1, 1], [1, 1]]
# ret2 = solution(n2, garden2)
#1인 지점을 큐에 넣고 시작하자
n3 = 4
garden3 = [[1, 1, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
ret3 = solution(n3, garden3)
print(ret3)
BFS_이차원리스트_한개시작점
# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
from collections import deque
def BFS(n, position) :
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
visited = [[False] * (n) for _ in range(n)]
distance = [[0] * (n) for _ in range(n)]
dq = deque(position) #1 좌표 큐에 넣기
while dq : #dq가 빌때까지
now_x, now_y = dq.popleft()
visited[now_x][now_y] = True #방문처리
print(now_x, now_y)
for d in range(4) :
next_x = now_x + dx[d]
next_y = now_y + dy[d]
if 0 <= next_x < n and 0 <= next_y < n and visited[next_x][next_y] is False :
dq.append((next_x, next_y))
distance[next_x][next_y] = distance[now_x][now_y] + 1
print(visited)
print(distance)
def solution(n, garden):
answer = 0
position = []
for i in range(n) :
for j in range(n) :
if garden[i][j] == 1 :
position.append((i, j))
BFS(n, position)
return answer
n1 = 3
mpas = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
ret1 = solution(n1, mpas)
BFS_이차원리스트_한번씩방문
from collections import deque
#BFS 현재 좌표는 pop, 다음으로 갈 인접 좌표 큐에 push
def BFS(start_x, start_y) :
dx = [-1, 0, 1, 0] #위 0, 오른 1, 아래쪽 2, 왼쪽 3
dy = [0, 1, 0, -1]
dq = deque() #BFS를 위한 큐 생성
visite_list = [[False] * row for _ in range(row)]
dq.append((start_x, start_y)) #1. 큐에 시작점 추가
visite_list[start_x][start_y] = True #2. 큐에 넣은 시작점은 방문처리
#BFS 시작
while dq : #3. 큐가 텅 빌때까지 방문
now_idx = dq.popleft() #큐에는 [(x, y)] 좌표 들어감
for d in range(4) : #위 0, 오른 1, 아래쪽 2, 왼쪽 3 방향 반복하면서 큐에 4방향 순회
next_x = now_idx[0] + dx[d] #큐에 들어간 좌표 중 다음 x좌표[0]
next_y = now_idx[1] + dy[d] #큐에 들어간 좌표 중 다음 y좌표[1]
#x좌표 내 and y좌표 내에서 이동 and 이미 방문한 곳은 방문하지 않음
if 0 <= next_x <= (row-1) and 0 <= next_y <= (row-1) and visite_list[next_x][next_y] is not True:
print("[", map_data[next_x][next_y],"] :", next_x, next_y)
visite_list[next_x][next_y] = True #방문한 곳은 재방문 방지를 위해 True 처리
dq.append((next_x, next_y))
row = 5 #n*n 행렬 너비 입력
map_data = [[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25]]
#데이터 입력인 경우
# for i in range(row) : #맵 데이터 입력 받아서 맵 생성
# map_data.append(list(map(int, input().split())))
BFS(0, 0) #0,0 부터 시작
print(map_data)
DFS_그래프_인접구역탐색
# x부터 시작해서 DFS하여 그 순서를 출력하는 함수
# 단 visited에 방문기록 있음
def DFS(node) :
visited[node] = True
print(node, end = " ") #방문한 노드 출력
#node의 다음 연결된 노드 탐색
for next in graph[node] :
if visited[next] is False :
DFS(next)
vertex_n, edge_n = 9, 12
graph = [[] for _ in range(vertex_n+1)]
visited = [False] * (vertex_n+1)
input_data = [[1, 2],
[1, 3],
[2, 3],
[2, 4],
[2, 6],
[3, 7],
[4, 5],
[4, 7],
[4, 8],
[5, 6],
[7, 8],
[8, 9]]
#노드간의 이동 가능 경로 표기
for data in input_data :
vertex, edge = data
graph[vertex].append(edge)
graph[edge].append(vertex)
print(visited)
print(graph)
#graph[1]부터 탐색 시작
DFS(1)
#입력
# 9 12
# 1 2
# 1 3
# 2 3
# 2 4
# 2 6
# 3 7
# 4 5
# 4 7
# 4 8
# 5 6
# 7 8
# 8 9
DFS_그래프_최장경로길이
def DFS(node, count) :
global maxValue
visited[node] = True #현재 노드는 방문처리
#더 많은 경로를 갔다왔으면 최대 경로 갱신
if count > maxValue :
maxValue = count
#node의 다음 연결된 노드 탐색
for next in graph[node] :
if visited[next] is False :
DFS(next, count+1) #다음 노드로 간다
visited[next] = False #방문다녀온곳 방문처리 해제
input_data = [[1, 2],
[1, 3],
[2, 3],
[2, 4],
[2, 6],
[3, 7],
[4, 5],
[4, 7],
[4, 8],
[5, 6],
[7, 8],
[8, 9]]
vertex_n, edge_n = 9, 12
graph = [[] for _ in range(vertex_n + 1)] #안접 리스트 생성
visited = [False] * (vertex_n + 1)
maxValue = 0 #최장 경로 길이 초기화
#노드간의 이동 가능 경로 표기
for data in input_data :
vertex, edge = data
graph[vertex].append(edge) #무방향 그프
graph[edge].append(vertex) #무방향 그프
#인접 리스트 방문
#시작 노드를 정하기 위해서 for문 돌기
#시작점을 계속 변경하면서 최장 경로를 찾아준다
for i in range(1, vertex_n+1) :
visited[i] = True #시작 노드 방문처리
DFS(i, 1) #i 시작 노드도 1개로 세기 때문에 count는 1부터 시작한다.
visited[i] = False #시작 노드 방문 방문 초기화
print(maxValue)
#n개의 정점과 m개의 간선
#무방향 그래프에서 최장 경로를 구해라
DFS_이차원리스트_떨어져있는구역방문
def DFS(current_x, current_y, map_data) :
global count
global n
dx = [-1, 0, 1, 0] #top, right, bottom, light
dy = [0, 1, 0, -1]
count += 1
#이미 방문한 곳은 재방문 하지 않기 위해 0처리
map_data[current_x][current_y] = 0 #DFS 다 끝나면 해당 구역은 다 0처리됨
for d in range(4) :
next_x = current_x + dx[d]
next_y = current_y + dy[d]
if 0 <= next_x < n and 0 <= next_y < n and map_data[next_x][next_y] == 1:
DFS(next_x, next_y, map_data)
def solution() :
global n
global count
n = 7
map_data = [[0, 1, 1, 0, 1, 0, 0],
[0, 1, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 0, 0, 0]]
result = []
#완전 탐색 하면서 1 있는 곳은 DFS 시작
for i in range(n) :
for j in range(n) :
if map_data[i][j] == 1 :
count = 0
DFS(i, j, map_data)
result.append(count)
print(result)
solution()
#입력
# 7
# 0 1 1 0 1 0 0
# 0 1 1 0 1 0 1
# 1 1 1 0 1 0 1
# 0 0 0 0 1 1 1
# 0 1 0 0 0 0 0
# 0 1 1 1 1 1 0
# 0 1 1 1 0 0 0
#=> 결과 3
#입력
# 7
# 1 1 0 0 0 1 0
# 0 1 1 0 1 1 0
# 0 1 0 0 0 0 0
# 0 0 0 1 0 1 1
# 1 1 0 1 1 0 0
# 1 0 0 0 1 0 0
# 1 0 1 0 1 0 0
#=> 결과 5
DFS_이차원리스트_임의의출발지,목적지
# 출발지는 map_data의 최소값
# 도착지는 map_data의 최대값
# top, right, bottom, left 중 현재 값보다 큰 쪽으로만 이동
# 출발지에서 도착지까지 가는 경우의 수 구하기
def DFS(current_x, current_y, end_x, end_y, n) :
global map_data
global visite_list
global count
dx = [-1, 0, 1, 0] #위쪽 0, 오른쪽 1, 아래 2, 왼쪽 3
dy = [0, 1, 0, -1]
#목적지 x, y에 도달하는 경우, 방법의 수 카운트
if current_x == end_x and current_y == end_y :
count += 1
else :
for d in range(4) :
next_x = current_x + dx[d]
next_y = current_y + dy[d]
#x좌표, y좌표는 범위 내 and 방문하지 않은 경우(visite_list[next_x][next_y] is False)
#top, right, bottom, left 중 현재 값보다 큰 경우에만 다음 방문
if 0 <= next_x <= (n-1) and 0 <= next_y <= (n-1) and visite_list[next_x][next_y] is False and map_data[next_x][next_y] > map_data[current_x][current_y] :
visite_list[next_x][next_y] = True
DFS(next_x, next_y, end_x, end_y, n)
visite_list[next_x][next_y] = False
def solution() :
global map_data
global visite_list
global count
n = 5
map_data = [[2, 23, 92, 78, 93],
[59, 50, 48, 90, 80],
[30, 53, 70, 75, 96],
[94, 91, 82, 89, 93],
[97, 98, 95, 96, 100]]
visite_list = [[False] * n for _ in range(n)]
min = 2147000000
max = -2147000000
count = 0
for i in range(len(map_data)) :
for j in range(len(map_data)):
if map_data[i][j] < min :
min = map_data[i][j] #출발지 최소값 x좌표, y좌표 찾기
start_x = i
start_y = j
if map_data[i][j] > max : #목적지 최대값 x좌표, y좌표 찾기
max = map_data[i][j]
end_x = i
end_y = j
visite_list[start_x][start_y] = True
DFS(start_x, start_y, end_x, end_y, n)
print(count)
solution()
# 5
# 2 23 92 78 93
# 59 50 48 90 80
# 30 53 70 75 96
# 94 91 82 89 93
# 97 98 95 96 100
#정답 : 5
DFS_이차원리스트_중복방문가능
def DFS(L, current_x, current_y, number):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
if L == 5:
if number not in result:
result.append(number)
return
for d in range(4):
next_x = current_x + dx[d]
next_y = current_y + dy[d]
if 0 <= next_x < n-1 and 0 <= next_y < n-1:
DFS(L+1, next_x, next_y, number + board[next_x][next_y])
n = 5
board = []
result = []
board = [['1', '2', '3', '4', '5'],
['6', '7', '8', '9', '10'],
['11', '12', '13', '14', '15'],
['16', '17', '18', '19', '20'],
['21', '22', '23', '24', '25']]
# board = [[1, 2, 3, 4, 5],
# [6, 7, 8, 9, 10],
# [11, 12, 13, 14, 15],
# [16, 17, 18, 19, 20],
# [21, 22, 23, 24, 25]]
for i in range(n):
for j in range(n):
DFS(0, i, j, board[i][j])
print(result)
DFS_이차원리스트_한번씩방문
#DFS
#1. 현재 지점에 방문한다
#2. 인접한 지점을 보고 방문할 수 있는 점이 있는지 찾는다.
#3. 그 지점을 바로방문한다
width, height = 5, 5
visite_list = [[False] * height for _ in range(width)] #DFS를 위한 방문 확인용 리스트
map_data = [] #슬라임 개수
map_data = [[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25]]
# for _ in range(width) :
# map_data.append(list(map(int, input().split()))) #슬라임 데이터 맵
def DFS(current_x, current_y) :
dx = [-1, 0, 1, 0] #위쪽 0, 오른쪽 1, 아래 2, 왼쪽 3
dy = [0, 1, 0, -1]
visite_list[current_x][current_y] = True #방문처리
print(map_data[current_x][current_y])
for d in range(4) :
next_x = current_x + dx[d]
next_y = current_y + dy[d]
if 0 <= next_x <= (width-1) and 0 <= next_y <= (height-1) : #범위 밖으로 나가지 않음
if visite_list[next_x][next_y] is not True : #방문하지 않았던 곳은 방문
DFS(next_x, next_y)
start_x, start_y = 0, 0 #0,0 부터 BFS 시작
DFS(start_x, start_y) #90점
print(visite_list)'코테풀이 > 코테용 파이썬 문법' 카테고리의 다른 글
| 재귀함수, DFS를 시각화로 보여주는 사이트 (0) | 2022.07.21 |
|---|---|
| 문자열_정규식_정규식패턴 (0) | 2022.07.01 |
| 문자열_알파벳_한글_숫자_특수문자_구분 (0) | 2022.07.01 |
| 람다_딕셔너리_튜플_정렬 (0) | 2022.07.01 |
| 0_사용_import (0) | 2022.07.01 |
BFS, DFS