전력망 둘로 나누기
BFS
-
발견한문제 : bfs의 기초 부족
-
-> 기초 문제다시풀어야 겠다….
```python from collections import deque
node = [[0] * 100 for _ in range(100)] edge = [0 for i in range(100)] visited = [0 for i in range(100)]
def bfs(graph, queue): global n global visited
while queue:
v = queue.popleft()
# vertex에 연결된 edge의 개수 구하기
print(v, end = ' ')
n = edge[v]
for i in range(n, -1, -1):
next = node[v][n]
# 이미 네모칸을 방문했다면 무시
if visited[next] == 1:
continue
# 방문안한 vertex들을 queue에 넣음
queue.append(next)
visited[next] = 1
return
def solution(n, wires): global m global visited
graph = []
answer = []
# 그래프 그리기
for i in range(len(wires)):
for w in wires:
if wires[i] != w:
node[w[0]][edge[w[1]]] = w[1]
node[w[1]][edge[w[0]]] = w[0]
edge[w[0]] += 1
edge[w[1]] += 1
result = 0
# bfs를 통해 연결되어 있는 덩어리의 개수를 구해보자
for i in range(1, n + 1):
queue = deque()
queue.append(i)
if visited[i] == 0:
visited[i] = 1
bfs(edge, queue)
result += 1
print('result:', result)
n = 9 wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] solution(n, wires)
1 0 2 3 4 5 6 7 8 9 result: 8
* 왜 갑자기 0번 vertex를 방문하냐? ㅋㅋㅋ 개 뜬금없네... 무슨 문제지??? 흠...... 그리고 result 8은 무슨 일이냐?...
```python
from collections import deque
def bfs(graph, queue, node, edge):
global n
global visited
while queue:
v = queue.popleft()
# vertex에 연결된 edge의 개수 구하기
# print(v, end = ' ')
n = edge[v]
for i in range(n, -1, -1):
next = node[v][i]
# 이미 네모칸을 방문했다면 무시
if visited[next] == 1:
continue
# 방문안한 vertex들을 queue에 넣음
queue.append(next)
visited[next] = 1
return
def solution(n, wires):
global m
global visited
graph = []
answer = []
# 그래프 그리기
for i in range(len(wires)):
node = [[0] * 100 for _ in range(100)]
edge = [0 for i in range(100)]
visited = [0 for i in range(100)]
# 끊고싶은 wire 1개 선택
for w in wires:
# wire 1개 끊으면, 그래프 그리기
if wires[i] != w:
node[w[0] - 1][edge[w[1]]] = w[1] - 1
node[w[1] - 1][edge[w[0]]] = w[0] - 1
edge[w[0] - 1] += 1
edge[w[1] - 1] += 1
result = 0
# bfs를 통해 연결되어 있는 덩어리의 개수를 구해보자
for j in range(0, n):
queue = deque()
queue.append(j)
if visited[j] == 0:
visited[j] = 1
bfs(edge, queue, node, edge)
result += 1
print(result)
# answer.append(result)
print(answer)
n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
solution(n, wires)
-
이제 순회를 하긴 하는데, 덩어리가 몇개인지는 잘 모르는구나 ~~ 아직 …. 원인…..
-
킹리적 갓심은 이 코드에 숨어있다.
node[w[0] - 1][edge[w[1]]] = w[1] - 1 node[w[1] - 1][edge[w[0]]] = w[0] - 1 edge[w[0] - 1] += 1 edge[w[1] - 1] += 1- 이것은 dfs를 위한 자료셋팅 같아서,,,, 문제다….
- 그림을 보면, vertex 3과 연결된 vertex의 개수는 3개인데, node[v]를 보면은 4만 연결되어 있다고 나온다… 여기서 근본적인 문제의 원인이 있는것이다.
이제 문제를 찾았다.
edge[w[0]] += 1 edge[w[1]] += 1 node[w[0]][edge[w[0]]] = w[1] node[w[1]][edge[w[1]]] = w[0]
- node 배열에 정보를 넣을때 문제가 생긴것이다. 이제 깔끔하게 bfs한다…
전선을 안그었을때 완벽한 bfs코드
from collections import deque
def bfs(queue, node, edge, visited, n):
connected = 0
while queue:
v = queue.popleft()
# vertex에 연결된 edge의 개수 구하기
#print(v, end = ' ')
connected += 1
k = edge[v]
for i in range(1, k + 1):
next = node[v][i]
# 이미 네모칸을 방문했다면 무시
if visited[next] == 1:
continue
# 방문안한 vertex들을 queue에 넣음
queue.append(next)
visited[next] = 1
return (connected, n - connected)
def solution(n, wires):
node = [[0] * 100 for _ in range(100)]
edge = [0 for i in range(100)]
visited = [0 for i in range(100)]
# 그래프 그리기
for w in wires:
edge[w[0]] += 1
edge[w[1]] += 1
node[w[0]][edge[w[0]]] = w[1]
node[w[1]][edge[w[1]]] = w[0]
result = 0
answer = []
# bfs를 통해 연결되어있는 덩어리의 개수를 구해보자
for j in range(1, n):
queue = deque()
queue.append(j)
if visited[j] == 0:
visited[j] = 1
c, u = bfs(queue, node, edge, visited, n)
result += 1
answer.append([c, u])
print(answer)
n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
solution(n, wires)
전선을 그었을때 완벽한 코드
from collections import deque
def bfs(queue, node, edge, visited, n):
connected = 0
while queue:
v = queue.popleft()
# vertex에 연결된 edge의 개수 구하기
#print(v, end = ' ')
connected += 1
k = edge[v]
for i in range(1, k + 1):
next = node[v][i]
# 이미 네모칸을 방문했다면 무시
if visited[next] == 1:
continue
# 방문안한 vertex들을 queue에 넣음
queue.append(next)
visited[next] = 1
return (connected, n - connected)
def solution(n, wires):
answer = []
for i in range(len(wires)):
node = [[0] * 100 for _ in range(100)]
edge = [0 for i in range(100)]
visited = [0 for i in range(100)]
# 그래프 그리기
for w in wires:
if wires[i] != w:
edge[w[0]] += 1
edge[w[1]] += 1
node[w[0]][edge[w[0]]] = w[1]
node[w[1]][edge[w[1]]] = w[0]
result = 0
# bfs를 통해 연결되어있는 덩어리의 개수를 구해보자
for j in range(1, n):
queue = deque()
queue.append(j)
if visited[j] == 0:
visited[j] = 1
c, u = bfs(queue, node, edge, visited, n)
result += 1
val = abs(c - u)
print(f'val = {val}')
answer.append(val)
return (min(answer))
- 다만, 정확성 84.6을 가지고 2개의 케이스에서 런타임에러가 난다. 쓸데없이 bfs를 많이해서 이런결과가 나타난것일지도 ….
더 잘풀려면
- 굳이 edge, node 만들지 말고, list에다가 바로 append하는 방식을 이용하자
- 이때는, 간선간의 길이가 1로 일정해서 그래도 됨 ㅎ
import sys
from collections import defaultdict, deque
# 넓이우선탐색
def bfs(a, b, wire_node, n):
que = deque()
que.append(a)
visited = [0] * (n + 1)
visited[a] = 1
cnt = 0
while que:
tmp = que.popleft()
for next_wire in wire_node[tmp]:
if tmp == a and next_wire == b:
continue
if visited[next_wire] == 0:
visited[next_wire] = 1
que.append(next_wire)
cnt += 1
return cnt
def solution(n, wires):
# 전력망 노드 생성
wire_node = defaultdict(list)
for a, b in wires:
wire_node[a].append(b)
wire_node[b].append(a)
# 전력망 끊기 순환
min_val = sys.maxsize # 최소값 초기화
for wire in wires:
cut1, cut2 = wire
val = abs(bfs(cut1, cut2, wire_node, n) - bfs(cut2, cut1, wire_node, n))
if val < min_val:
min_val = val
return min_val
기초문제
아이스크림
-
from collections import deque def bfs(i, j, table, visited): queue = deque() if table[i][j - 1] == 1: queue.push([i, j]) def solution(): n, m = map(int, input().split()) # 이 아래 2줄도 사실은 필요가 없는것이다. table = [[0] * (m + 2) for _ in range(n + 2)] visited = [[0] * m for _ in range(n)] # 테이블 셋팅, 그리고 입력을 이렇게 어렵게 받을 필요가 없는것 같고, 굳이 셋팅 조차 할 필요없다. for i in range(0, n + 2): for j in range(0, n + 2): if i == 0 or i == n + 1 or j == 0 or j == n + 1: table[i][j] = 2 else: num = int(input()) table[i][j] = num # 어떻게 간단하게 하냐면은, for i in range(n): graph.append(list(map(int, input())) # 이미 전 테이블이 나와있기때문에 굳이 i, j 인덱스 값기준으로 테이블을 작성할 필요가 없는것이다. # 순회하자 for i in range(n): for j in range(m): if visited[i][j] == 0: bfs(i, j, table, visited)- 이 문제는 입력으로 노드간의 연결조건이 아니라, 테이블 자체를 input으로 주기 때문에, 다른 방식으로 접근하는것이 좋을것 같다.
from collections import deque def dfs(i, j, n, m, graph): queue = deque() if i <= -1 or i >= n or j <= -1 or j >= m: return False if graph[i][j] == 0: graph[i][j] = 1 dfs(i + 1, j, n, m, graph) dfs(i - 1, j, n, m, graph) dfs(i, j + 1, n, m, graph) dfs(i, j - 1, n, m, graph) return True def solution(): n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) # 이미 전 테이블이 나와있기때문에 굳이 i, j 인덱스 값기준으로 테이블을 작성할 필요가 없는것이다. # 순회하자 result = 0 for i in range(n): for j in range(m): if dfs(i, j, n, m, graph) == True: result += 1 print(result) return result solution()- 위 두개 코드의 차이
- 첫번째 코딩은 Padding으로 일반화 과정을 한번 거쳤는데, 그게 그렇게 좋은 코딩은 아닌듯… 왜냐면 두번째 코딩에 if문으로 다처리 되니까 ㅋㅋㅋㅋ
- 일단, 이 문제는 bfs로 풀고 싶었는데 흠 dfs로또 풀었네…..
from collections import deque from re import L visited = [[0] * 100 for _ in range(100)] def bfs(graph, x, y, queue): global n global m global visited dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] depth = 0 while queue: v = queue.popleft() print(v, end = ' ') for i in range(4): nx = v[0] + dx[i] ny = v[1] + dy[i] # 확인할 네모칸이 범위 밖이면 무시 if nx < 0 or nx >= n or ny < 0 or ny >= m : continue # 이미 네모칸을 방문했다면 무시 if visited[nx][ny] == 1: continue if graph[nx][ny] == 0: queue.append([nx, ny]) visited[nx][ny] = 1 depth = depth + 1 return def solution(): global n global m global visited n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) # 이미 전 테이블이 나와있기때문에 굳이 i, j 인덱스 값기준으로 테이블을 작성할 필요가 없는것이다. result = 0 # 순회하자 for i in range(n): for j in range(m): queue = deque() queue.append([i, j]) # 이 조건문을 추가해줘서 겨우 문제를 풀었다.... 제일 중요한 조건 if visited[i][j] == 0 and graph[i][j] == 0: visited[i][j] = 1 bfs(graph, i, j, queue) result += 1 print(result) return solution()- 이번에는 bfs로 품 (dfs와 bfs의 차이는 사실 별로 없는것 같다. 문제의 상황마다 다를뿐이지)
미로찾기 (최단거리)
- 최단거리는 bfs로 푸는게 좋다(단, 간선의 길이가 같기 때문에) -> 간선의 길이가 같다면 bfs는 차근차근히 경로를 1씩 증가시키며 경로의 길이를 구하지만, dfs는 일단 끝까지 파고들기 때문에, 경로의 길이에 상관없이 모든 경로마다의 길이를 구한다.
from collections import deque def bfs(graph, x, y, queue): global n global m dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] depth = 0 while queue: v = queue.popleft() print(v, end = ' ') for i in range(4): nx = v[0] + dx[i] ny = v[1] + dy[i] if nx == n - 1 and ny == m - 1: print(depth) return depth # 확인할 네모칸이 범위 밖이면 무시 if nx < 0 or nx >= n or ny < 0 or ny >=m : continue # 이미 네모칸을 방문했다면 무시 if visited[nx][ny] == 1: continue if graph[nx][ny] == 1: queue.append([nx, ny]) visited[nx][ny] = 1 depth += 1 pass def solution(): global n global m global visited n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) # 이미 전 테이블이 나와있기때문에 굳이 i, j 인덱스 값기준으로 테이블을 작성할 필요가 없는것이다. # 순회하자 visited = [[0] * m for _ in range(n)] queue = deque() queue.append([1, 1]) visited[1][1] = 1 bfs(graph, 1, 1, queue) return solution()
Leave a comment