목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.
사용 언어
Python
일정
3회차: 7/20 14:00 ~ 17:00
목표 : 백준 BFS 알고리즘 관련 3 - 4 문제 풀기
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)
결과
촌수를 계산해야하므로 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)
결과
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)
결과