[Python] 코딩테스트 연습

2667번: 단지번호붙이기

from collections import deque

N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))
    
dx, dy = [1,-1,0,0], [0,0,1,-1]

def bfs(g, r, c):
    q = deque([(r, c)])
    g[r][c] = 0
    cnt = 1    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or N<=nx or ny<0 or N<=ny:
                continue
            if g[nx][ny] == 1:
                cnt += 1
                g[nx][ny] = 0
                q.append((nx, ny))
    return cnt

cnt_lst = []    
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            cnt_lst.append(bfs(graph, i, j))
            
cnt_lst.sort()
print(len(cnt_lst))
for c in cnt_lst:
    print(c)

---

11724번: 연결 요소의 개수

from collections import deque

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [False]*(N+1)
cnt = 0

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def bfs(start):
    q = deque([start])
    visited[start] = True
    while q:
        node = q.popleft()
        for adj_node in graph[node]:
            if not visited[adj_node]:
                visited[adj_node] = True
                q.append(adj_node)
      
for node in range(1, N+1):
    if visited[node]:
        continue
    visited[node] = True
    cnt += 1
    for adj_node in graph[node]:
        bfs(adj_node)
        
print(cnt)

 

---

14502번: 연구소

from collections import deque
import copy
from itertools import combinations

# 입력받기
N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

# 바이러스 위치
blank_position = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            blank_position.append((i, j))

# 벽을 설치할 후보지 조합
wall_candidates = combinations(blank_position, 3)

# bfs
dx, dy = [0,0,1,-1], [1,-1,0,0]
def bfs(g):
    q = deque()
    # 초기 바이러스 장소 큐에 넣기
    for i in range(N):
        for j in range(M):
            if g[i][j] == 2:
                q.append((i, j))
    # 바이러스 퍼트리기
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or N<=nx or ny<0 or M<=ny:
                continue
            if g[nx][ny] == 0:
                g[nx][ny] = 2
                q.append((nx, ny))

max_safe_area = 0
for walls in wall_candidates:
    safe_area = 0
    g = copy.deepcopy(graph)
    # 벽설치
    for p in walls:
        g[p[0]][p[1]] = 1
    # 바이러스 퍼짐
    bfs(g)
    # 안전지역 넓이 계산
    for i in range(N):
        for j in range(M):
            if g[i][j] == 0:
                safe_area += 1
    max_safe_area = max(max_safe_area, safe_area)

print(max_safe_area)