BAEKJOON : 1707, 2667, 2146

No. 2178

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")  

No. 2667

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')

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')

No. 2146

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)