# ---------- Import ----------
from collections import deque
import sys
input = sys.stdin.readline
# ---------- Function ----------
def is_Bipartite(graph, node_count):
visited = [-1] * (node_count+1)
for node in range(node_count+1):
# group1 number is 1, group2 number is 0
if visited[node] != -1:
continue
group = 1
visited[node] = group
Q = deque([(node, group)]) # node, group
while Q:
node, group = Q.popleft()
for i in graph[node]:
if visited[i] == group:
return "NO"
if visited[i] == -1:
visited[i] = (group+1) % 2
Q.append((i, (group+1) % 2))
return "YES"
# ---------- Main ----------
for _ in range(int(input())):
node, edge = map(int, input().split())
graph = [[] for _ in range(node+1)]
for _ in range(edge):
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s)
answer = is_Bipartite(graph, node)
print(answer)
Import 부분에서 다익스트라로 사용할 heapq와 빠른 입력을 위한 sys을 호출했다.
Function 부분에서 시작(sNode)과 끝노드(eNode)를 받는 다익스트라 함수를 작성한다.
Main 부분에서는 문제에서 주어진 입력을 받는다.
그리고 마지막에 가장 짧은 부분을 찾아 정답을 출력한다.
# ---------- Main ----------
Node, Edge = map(int, input().split())
graph = [[] for _ in range(Node+1)]
# Input graph information
for _ in range(Edge):
start, end, weight = map(int, input().split())
graph[start].append((end, weight))
graph[end].append((start, weight))
다익스트라 코딩 우선순위는 미뤘다.
왜냐하면 다익스트라는 이미 정해진 틀이 있기 때문이다. 즉, 다익스트라는 단순한 '계산'에 불과하다.
따라서 문제의 주의할 점과 흐름 작성이 먼저라고 생각하여 Main부터 작성하였다.
위의 코드는 N(Node)와 E(Edge), graph를 입력받는 부분이다.
이때 distance = [INF] * (Node+1) 부분은 지웠다. 이유는 문제에서 주어진다.
"한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다."
즉 START에서 fir, sec를 거쳐 END로 갈 때, 갔던 간선을 다시 이동할 수 있다는 이야기다.
그럼 연산을 나눠서 START에서 fir로, fir에서 sec로, sec에서 END로 가는 걸 따로 계산해야 한다는 말과 같다.
따라서 위의 distance 부분은 다익스트라를 호출할 때 초기화해줘야 한다. 그래서 함수 내부로 옮겨주었다.
그밖에 주의할 점은 문제에서 "방향성이 없는 그래프"라고 주어진다.
start를 기준으로 end에 추가한다면, end를 기준으로 start도 추가해줘야 한다.
# ---------- Main ----------
# Two node that must pass
fir, sec = map(int, input().split())
way_distance = [0, 0]
way_condition = [
[(1, fir), (fir, sec), (sec, Node)],
[(1, sec), (sec, fir), (fir, Node)]
]
fir와 sec를 거쳐가는 방법은 두 가지가 있다.
1. START > fir > sec > END
2. START > sec > fir > END
둘 중 무엇이 더 빠른 방법인지 모르니, 둘 다 계산하고 비교해야 한다.
따라서 way_distance에는 각 방법의 최소 거리를 저장하는 리스트로 선언하고,
way_condition에는 각 방법의 경로를 저장하는 2차원 리스트로 선언한다.
way_distance와 way_condition은 index를 기준으로 mapping한다.
# ---------- Main ----------
# Print answer
way1 = way_distance[0]
way2 = way_distance[1]
if (way1 is None) and (way2 is None): print(-1)
elif way1 is None: print(way2)
elif way2 is None: print(way1)
else: print(min(way1, way2))
문제에서 "그러한 경로가 없을 때에는 -1을 출력한다"라고 적혀있어서 의문이 들었다.
그럼 1번과 2번 경로가 모두 존재하지 않는 경우여야 하는 것 아닌가?
아 그러면 1번만 없을 때, 2번만 없을 때, 1번과 2번 모두 없을 때가 따로 존재하겠구나.
그래서 위의 형태로 코드를 작성했다.
이때 없다는 것을 확실하게 표현하기 위해 None으로 값을 할당했다.
# ---------- Main ----------
# Find shortest way
for idx, condition in enumerate(way_condition):
way = 0
for s, e in condition:
try:
way += Dijkstra(s, e)
except TypeError:
way = None
break
way_distance[idx] = way
가장 짧은 거리를 구하는 알고리즘이다.
경로가 존재하지 않는 경우를 None으로 하기로 했다. 하지만 최소 거리는 int 자료형이다.
Dijkstra 함수에서 경로가 없으면 None을 반환할 것이고, 이러면 TypeError가 발생한다.
NoneType과 Int는 서로 더할 수 없다. 따라서 try-except를 활용한다.
만약 중간에 한 번이라도 TypeError가 발생한다면, 해당 경로는 미완성이 된다.
따라서 except로 빠질 경우, way에 None을 할당하고, break로 빠져나온다.
그게 아니라면 계속해서 way에 최단 거리(Dijkstra(s, e))를 구하여 더해준다.
최종적으로 다 더한 way는 idx를 기준으로 way_distance에 접근하여 값을 저장한다.
기본적인 다익스트라 함수는 sNode(출발 노드)만 받아서, 전체 노드의 최단 거리를 반환한다.
하지만 이 문제에서는 굳이 그럴 필요가 없다고 생각했다.
기점과 종점이 정해져 있으니, 두 노드만 확인하면 되는 거 아닌가?
해서 sNode와 eNode 두 값을 매개변수로 받아들인다.
그 다음 자기 자신의 거리를 0으로 초기화하고, Q에 (cost, node)를 쌍으로 추가한다.
# ---------- Function ----------
# Do dijkstra
while Q:
cost, current_node = heapq.heappop(Q)
# End condition
if current_node == eNode:
return distance[eNode]
# Check nodes connected with current node
for next_node, weight in graph[current_node]:
new_cost = cost + weight
# New cost is more smallest
if new_cost < distance[next_node]:
distance[next_node] = new_cost
heapq.heappush(Q, (new_cost, next_node))
# No way to go eNode
return None
다익스트라 알고리즘에서 핵심인 부분이다.
Q가 존재한다면 계속해서 pop을 하면서 확인한다.
이때 꺼낸 node(current_node)가 입력받은 종점(eNode)과 일치한다면 조기 종료한다.
내가 원하는 것은 기점과 종점 사이의 최단 거리뿐이지, 다른 것은 불필요하다.
아니라면 current_node와 연결된 값들을 하나하나 둘러본다(graph[current_node]).
이때 새로운 거리(new_cost)가 기존의 거리(distance[next_node])보다 작다면, 업데이트한다.
위 과정을 전부 돌았음에도 불구하고 조기 종료가 되지 않을 수 있다.
이 말은 종점으로 가는 길을 찾지 못했다는 말이다.
return None으로 '갈 수 없음'을 반환하고 함수를 종료한다.
다행히도 이번에는 놓친 부분이 없었다.
한 번에 AC를 받을 수 있었다.
친구가 코딩 테스트 연습을 할 때 스톱워치를 켜두고 문제를 푼다고 했다.
자기가 얼마나 시간을 소모했고, 얼마나 줄여야 하는지 눈에 보인다고 하길래 이번에 시간을 측정해봤다.
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Main ----------
people, M = map(int, input().split())
truthy = set(list(map(int, input().split()))[1:])
parties = [set(list(map(int, input().split()))[1:]) for _ in range(M)]
for _ in range(M):
for party in parties:
if party & truthy:
truthy = truthy.union(party)
cnt = 0
for party in parties:
if party & truthy: continue
cnt += 1
print(cnt)
# ---------- Import ----------
from collections import deque
import sys
input = sys.stdin.readline
# ---------- Function ----------
def BFS(row, col, graph, visited):
# UP, DN, LFT, RGT
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque([(x, y) for x in range(row) for y in range(col) if graph[x][y] == 2])
visited[queue[0][0]][queue[0][1]] = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<row and 0<=ny<col and visited[nx][ny] == -1:
if graph[nx][ny] == 0:
visited[nx][ny] = 0
elif graph[nx][ny] == 1:
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))
return visited
# ---------- Main ----------
row, col = map(int, input().split())
map_ = [list(map(int, input().split())) for _ in range(row)]
visited = [[-1] * col for _ in range(row)]
visited = BFS(row, col, map_, visited)
for r in range(row):
for c in range(col):
if not map_[r][c]: print(0, end=" ")
else: print(visited[r][c], end=" ")
print()
# ---------- Import ----------
from collections import deque
import sys
input = sys.stdin.readline
# ---------- Function ----------
def BFS(row, col, graph, visited):
queue = deque()
return
# ---------- Main ----------
row, col = map(int, input().split())
map_ = [list(map(int, input().split())) for _ in range(row)]
ㅇㅇ
# ---------- Main ----------
visited = [[-1] * col for _ in range(row)]
visited = BFS(row, col, map_, visited)
for line in visited:
print(*line)
ㅇㅇ
# ---------- Function ----------
def BFS(row, col, graph, visited):
# UP, DN, LFT, RGT
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque([(x, y) for x in range(row) for y in range(col) if graph[x][y] == 2])
visited[queue[0][0]][queue[0][1]] = 0
return visited
ㅇㅇ
# ---------- Function ----------
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<row and 0<=ny<col and visited[nx][ny] == -1:
if graph[nx][ny] == 0:
visited[nx][ny] = 0
elif graph[nx][ny] == 1:
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))
# -------------------- Case 1 --------------------
# ---------- Import ----------
from itertools import combinations
from collections import deque
import copy
import sys
input = sys.stdin.readline
# ---------- Function ----------
def BFS(row: int, col: int, lab: list) -> int:
result = 0
FLAG = 0
# UP, DN, LFT, RHT
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# Checking empty(0) area that can be build a wall
empty_space = [(x, y) for x in range(row) for y in range(col) if lab[x][y] == 0]
for empty in combinations(empty_space, 3):
graph = copy.deepcopy(lab)
# Build a wall using combinations
for wallX, wallY in empty:
graph[wallX][wallY] = 1
# Checking virus(2) area
queue = deque([(x, y) for x in range(row) for y in range(col) if graph[x][y] == 2])
# queue = deque((x, y) for x in range(row) for y in range(col) if graph[x][y] == 2)
# Starting BFS
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<row and 0<=ny<col and graph[nx][ny] == 0:
graph[nx][ny] = 2
queue.append((nx, ny))
# Checking safe(0) area
cnt = 0
for line in graph:
cnt += line.count(0)
result = max(cnt, result)
return result
# ---------- Main ----------
row, col = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(row)]
result = BFS(row, col, lab)
print(result)
1번 풀이, 파이썬 라이브러리 combinations를 활용한 방법
Python3에서도 시간 초과없이 무난하게 통과 가능하다.
# -------------------- Case 2: TLE (Pypy3: AC) --------------------
# ---------- Import ----------
from collections import deque
import copy
import sys
input = sys.stdin.readline
# ---------- Function ----------
def BFS():
queue = deque()
graph = copy.deepcopy(lab)
# Checking virus location
for r in range(row):
for c in range(col):
if graph[r][c] == 2:
queue.append([r, c])
# BFS calculating
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= row or ny >= col: continue
if graph[nx][ny] == 1 or graph[nx][ny] == 2: continue
if graph[nx][ny] == 0:
graph[nx][ny] = 2
queue.append([nx, ny])
# Count '0' area
global result
cnt = 0
for r in range(row):
for c in range(col):
if graph[r][c] == 0:
cnt += 1
result = max(result, cnt)
return
def makeWall(cnt: int):
# Wall is 3, then BFS
if cnt == 3:
BFS()
return
# Making wall using backtracking
for r in range(row):
for c in range(col):
if lab[r][c] == 0:
lab[r][c] = 1
makeWall(cnt + 1)
lab[r][c] = 0
return
# ---------- Main ----------
row, col = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(row)]
# UP, DN, LFT, RGT
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
result = 0
makeWall(0)
print(result)
많은 BFS 문제를 풀어봤다면 익숙할 네 방향으로 이동하기 위한 dx, dy 리스트도 선언해준다.
# ---------- Import ----------
import copy
# ---------- Function ----------
# Checking empty(0) area that can be build a wall
empty_space = [(x, y) for x in range(row) for y in range(col) if lab[x][y] == 0]
for empty in combinations(empty_space, 3):
graph = copy.deepcopy(lab)
# Build a wall using combinations
for wallX, wallY in empty:
graph[wallX][wallY] = 1
# Checking virus(2) area
queue = deque([(x, y) for x in range(row) for y in range(col) if graph[x][y] == 2])
lab에서 우선 빈 공간(0)의 위치들을 알아내야 한다. 그래야 combinations으로 조합이 가능하기 때문이다.
comprehension으로 (x, y)를 알아낸 뒤, empty_space에 저장한다.
그리고 for문으로 가능한 모든 조합의 수에 대해서 반복을 진행한다.
이때 BFS를 진행해야 하는데, 한 번 진행하고 나면 기존 BFS는 없어지기에 이를 유지할 필요가 생겼다.
파이썬의 copy 라이브러리를 사용하여 기존의 lab을 유지해준다.
└ graph = lab을 해주면 이는 얕은 복사라 값이 같이 바뀐다. 깊은 복사를 위해 deepcopy를 해줘야 한다.
이러면 empty 변수에는 ((0, 1), (0, 2), (0, 3)) 다음에 ((0, 1), (0, 2), (0, 4)) 이런 식으로 3개의 벽 위치가 들어온다.
for문으로 돌면서 벽 위치를 1로 바꿔준다.
그리고 queue에 virus의 위치를 저장한다. 이 또한 for와 if의 comprehension으로 작성해주었다.
이때 BFS를 사용해야 하기에 deque로 저장했다.
# ---------- Function ----------
# Starting BFS
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<row and 0<=ny<col and graph[nx][ny] == 0:
graph[nx][ny] = 2
queue.append((nx, ny))
# Checking safe(0) area
cnt = 0
for row in graph:
cnt += row.count(0)
result = max(cnt, result)
일반적인 BFS 함수 부분이다.
x, y를 queue 가장 왼쪽(첫 번째) 원소를 꺼내어 저장한 다음, 네 방향을 계산한다.
이때 범위를 벗어나지 않고, 갈 수 있는 상황(0)이라면,
바이러스가 퍼진 상태(2)로 바꾸고, 그 위치를 virus의 위치를 나타내는 queue에 저장한다.
마지막으로 cnt 변수에 각 combinations 경우에 대한 0 개수를 저장한다.
result와 비교하여 더 큰 값을 result에 저장하고 마지막으로 return한다.
이러면 함수 작성을 완료다. 코드가 길어지기는 하지만 생각보다는 풀만한 문제였다.
queue = deque((x, y) for x in range(row) for y in range(col) if graph[x][y] == 2)
^^^^^^^^^^
TypeError: 'list' object cannot be interpreted as an integer
그리고 에러가 떴다.
range(row)가 list라서 range() 사용이 불가능하다...?
분명 int로 받아줬는데 왜 자꾸 list 타입으로 뜨는 건지 이해할 수 없었다.
breakpoint() 함수로 확인해보니 처음은 <int>로 나오지만 두 번째부터는 <list>로 인식했다.
그럼 처음은 문제가 없지만, 한 바퀴 돌고 나서 문제이니... 코드에서 에러가 있다는 거였다.
int를 list로 바꿔주는 식의 형변환 코드는 없고... row 변수에서 문제가 생겼으니 row 변수를 확인해봤다.
아
마지막 코드 for row in graph에서 row 변수를 한 번 더 사용했다...
여기서 list를 덮어써서 제대로 동작하지 않은 것이었다.
변수 사용함에 있어서도 제대로 확인을 해줘야겠다.
# Before
cnt = 0
for row in graph:
cnt += row.count(0)
result = max(cnt, result)
# After
cnt = 0
for line in graph:
cnt += line.count(0)
result = max(cnt, result)
겹치는 row 변수에서 line이라는 다른 변수로 바꿔주었다.
그랬더니 정상적으로 코드가 실행되었다.
다행히 시간 초과가 뜨지 않고 정상적으로 완료했다.
백트래킹으로 작성하는 것도 한번 연습해봐야겠다.
└ 알아보니 백트래킹을 이용하면 Pypy3에서만 AC가 뜨고 Python3에서는 TLE가 뜬다.
P.S.
전에는 이틀이나 사흘에 걸쳐 문제를 고민하고는 했는데...
어째 요즘에는 하루만에 끝나는 경우가 태반이다.
하루종일 시간을 잔뜩 갈아넣어서 하루만에 끝나는 건지... 생각이 늘어난 건지 구분이 가지 않는다.
