No. 2178
1. Problem
2. My Solution
- 두 집합의 노드를 'red', 'black' 으로 나누어 번갈아 색을 칠해나감
- 도착한 노드와 인접한 다음 노드의 색이 같으면 이분 그래프 X
- 그래프의 정점이 모두 연결된 것은 아닐 수도 있으므로 여러 정점에서 출발하는 dfs 를 구현해야함
import sys
sys.setrecursionlimit(10**8)
def dfs(v,color):
global flag
visited[v] = color
for u in graph[v]:
if visited[u] == False and color == 'red':
dfs(u,'black')
elif visited[u] == False and color == 'black':
dfs(u,'red')
elif visited[u] == color:
flag = True
test_n = int(sys.stdin.readline())
for _ in range(test_n):
v,e = map(int,sys.stdin.readline().rstrip().split())
graph = [[] for _ in range(v+1)]
visited = [False] * (v+1)
flag = False
for _ in range(e):
a,b = map(int,sys.stdin.readline().rstrip().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1,v+1):
if visited[i] == False:
dfs(i,'red')
if flag == True:
print("NO")
else:
print("YES")
3. Learned
- 이분 그래프에 대해 알게됨 참고블로그
No. 2667
1. Problem
2. My Solution
- DFS 알고리즘을 이용해 문제 해결
import sys
def dfs(x,y):
global count_home
complex[x][y] = 0
for dx,dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < n and complex[nx][ny] == 1:
count_home += 1
dfs(nx,ny)
n = int(sys.stdin.readline())
complex = []
count_complex = 0
count_homes = []
move = [(-1,0),(1,0),(0,-1),(0,1)]
for _ in range(n):
complex.append(list(map(int,list(sys.stdin.readline().rstrip()))))
for i in range(n):
for j in range(n):
if complex[i][j] == 1:
count_home = 1
dfs(i,j)
count_homes.append(count_home)
count_complex += 1
print(count_complex)
print(*sorted(count_homes), sep='\n')
- BFS 알고리즘을 이용해 문제 해결
import sys
from collections import deque
def bfs(x,y):
global count_home
queue = deque()
queue.append((x,y))
complex[x][y] = 0
while(queue):
x,y = queue.popleft()
for dx,dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < n and complex[nx][ny] == 1:
count_home += 1
queue.append((nx,ny))
complex[nx][ny] = 0
n = int(sys.stdin.readline())
complex = []
count_complex = 0
count_homes = []
move = [(-1,0),(1,0),(0,-1),(0,1)]
for _ in range(n):
complex.append(list(map(int,list(sys.stdin.readline().rstrip()))))
for i in range(n):
for j in range(n):
if complex[i][j] == 1:
count_home = 1
bfs(i,j)
count_homes.append(count_home)
count_complex += 1
print(count_complex)
print(*sorted(count_homes), sep='\n')
3. Learned
- 입력을 map 이라는 변수로 저장하면 map 함수와 충돌되기 때문에 예약어 및 함수명으로는 변수 설정을 하지 말자
No. 2146
1. Problem
2. Others' Solutions
- BFS 를 통해 섬마다 고유 id 를 부여
- bfs_search 에서 visited 를 매번 초기화
- queue 에 삽입할 때 x,y 좌표 뿐만 아니라 depth 정보 또한 저장
- 입력 N <= 100 이므로 각 위치마다 BFS 를 수행해도 최대 N^2 = 10000
- 각 위치 마다 다른 섬까지의 거리를 구하는 복잡도 또한 최대 N^2 = 10000
import sys
import math
from collections import deque
def bfs_id(x,y,id):
queue = deque()
queue.append((x,y))
world[x][y] = id
while(queue):
x,y = queue.popleft()
for dx,dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < n and world[nx][ny] == 1:
queue.append((nx,ny))
world[nx][ny] = id # 섬에 id 지정
def bfs_search(x,y,id):
global res
queue = deque()
visited = [[False] * n for _ in range(n)]
queue.append((x,y,0)) # depth 정보 또한 가지고 있음
while(queue):
x,y,count = queue.popleft()
if res <= count:
return
for dx,dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == False:
if world[nx][ny] == id: # 같은 섬 안이면 넘어감
continue
elif world[nx][ny] == 0: # 바다면 건너감
queue.append((nx,ny,count+1))
visited[nx][ny] = True
else: # 다른 섬이면 지금까지 온 거리와 res 비교
res = min(res, count)
n = int(sys.stdin.readline())
world = []
move = [(-1,0),(1,0),(0,-1),(0,1)]
id = 2
res = math.inf
for _ in range(n):
world.append(list(map(int,sys.stdin.readline().rstrip().split())))
for i in range(n): # 섬에 고유 id 지정
for j in range(n):
if world[i][j] == 1:
bfs_id(i,j,id)
id += 1
for i in range(n): # 특정 섬에서 다른 섬까지 거리 구함
for j in range(n):
if world[i][j] != 0:
bfs_search(i,j,world[i][j])
print(res)
3. Learned
- bfs 수행과정에서 queue 에 다음 노드를 저장할 때 추가적인 정보 또한 저장할 수 있음 (depth)
