[2022 하계 모각코] 팀 "한 명 어디갔노" 3회차 - 계획 및 결과

목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.

사용 언어
Python

일정
3회차: 7/20 14:00 ~ 17:00
목표 : 백준 BFS 알고리즘 관련 3 - 4 문제 풀기

1. 백준 2606번
   

BFS, DFS 어느 것을 사용해도 풀리는 문제지만 BFS를 사용하여 풀어보았다.

Code

cnt = 0
def bfs(virus):
    global cnt
    visited[virus] = 1
    queue = [virus]
    while queue:
        for i in relation[queue.pop()]:
            if (visited[i] == 0):
                visited[i] = 1
                queue.insert(0, i)
                cnt += 1

n = int(input())
link = int(input())

relation = [[] * (n + 1) for _ in range(n + 1)]

for i in range(link):
    a, b = map(int, input().split())
    relation[a].append(b)
    relation[b].append(a)

visited = [0] * (n + 1)
bfs(1)
print(cnt)

결과

2. 백준 2644번
   

촌수를 계산해야하므로 BFS 탐색하면서 촌수를 갱신하는 방식으로 풀어보았다.

Code

from collections import deque
import sys

input = sys.stdin.readline
n = int(input())

a, b = map(int, input().split())

m = int(input())

relation = [[] for i in range(n + 1)]
result = [0 for i in range(n + 1)]

def bfs(start):
    q = deque()
    q.append(start)
    visit = [0 for i in range(n + 1)]
    visit[start] = 1
    while q:
        point = q.popleft()
        for i in relation[point]:
            if visit[i] == 0:
                visit[i] = 1
                result[i] = result[point] + 1
                q.append(i)

for i in range(m):
    x, y = map(int, input().split())
    relation[x].append(y)
    relation[y].append(x)

bfs(a)
if result[b] != 0:
    print(result[b])
else:
    print(-1)

결과

3. 백준 10026번
   

BFS방식으로 푸는 것은 같지만 적록색약이 있는 경우와 없는 경우를 따로 생각해야하므로 적록색약이 없다는 가정하에 답을 먼저 산출하고 R을 G로 바꾸어 다시 BFS탐색을 진행하여 답을 구했다.

Code

from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    q.append([x, y])
    visited[x][y] = cnt
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if picture[nx][ny] == picture[x][y] and visited[nx][ny] == 0:
                    q.append([nx, ny])
                    visited[nx][ny] =1

n = int(input())
picture = [list(map(str, input())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
q = deque()

cnt = 0
for i  in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            bfs(i, j)
            cnt += 1
print(cnt, end = ' ')

for i  in range(n):
    for j in range(n):
        if picture[i][j] == 'R':
            picture[i][j] = 'G'
visited = [[0] * n for _ in range(n)]

cnt = 0
for i  in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            bfs(i, j)
            cnt += 1
print(cnt)

결과