[BOJ] 전쟁 - 전투 & 케빈 베이컨의 6단계 법칙 in Python

요 며칠 연휴여서 심심하기도 하고 오랜만에 알고리즘을 풀었습니다. 작정하고 어려운 문제를 건든게 아니어서.. 좀 쑥스럽네용..

케빈 베이컨의 6단계 법칙, 문제풀러가기!

전형적인 데이크스트라 문제로 간단하게 풀었습니다.

graph 만들고 실제로 순회할 부분만 따로 보기 위해 peoples라는 set을 만들었습니다. 문제에서 범위만 주어졌을 뿐이지 실제로 존재하는 노드가 1부터 차례로 시작인지는 확실하게 읽지를 않아서 확실한 node만 담기 위한 목적으로 서용했습니다.

다음은 똑같습니다. 데이크스트라 알고리즘을 사용하되, peoples에 있는 원소만 순회하여 문제에서 말한 level(제곱수의 합)을 구합니다. 그 중 가장 낮은 것을 찾으면 끝입니다.

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
INF = int(1e9)
peoples = set()

for _ in range(M):
    one, two = map(int, input().split())
    graph[one].append((1, two))
    graph[two].append((1, one))
    peoples.add(one)
    peoples.add(two)

peoples = list(peoples)
peoples.sort()

friends = [[0 for _ in range(N)] for _ in range(N)]

def dijkstra(start):
    
    init_dist = [INF for _ in range(N+1)]
    init_dist[start] = 0
    HQ = []
    heappush(HQ, (0, start))

    while HQ:
        cost, now = heappop(HQ)

        if init_dist[now] < cost: continue

        for add_cost, nxt in graph[now]:
            new_cost = cost + add_cost

            if init_dist[nxt] > new_cost:
                init_dist[nxt] = new_cost
                heappush(HQ, (init_dist[nxt], nxt))
    
    return init_dist

number = INF
answer = -1

for i in range(1, N+1):
    summm = sum(dijkstra(i)[1:])
    if number > summm:
        answer = i
        number = summm

print(answer)   

전쟁 - 전투, 문제풀러가기!

그냥 전형적인 dfs 문제

상 하 좌 우로 돌면서 dfs를 진행하되 전역으로 중요 정보를 관리, hash를 사용하여 답안 도출!

간단하게 풀었습니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [list(input().strip()) for _ in range(M)]
visited = [[False for _ in range(N)] for _ in range(M)]

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

dic = {
    "W": 0,
    "B": 0
}

def dfs(y, x):
    global num

    visited[y][x] = True

    for idx in range(4):
        nx, ny = x + dx[idx], y + dy[idx]

        if not (0 <= nx < N and 0 <= ny < M): continue
        if visited[ny][nx]: continue
        if graph[ny][nx] != target: continue
        num += 1
        dfs(ny, nx)


for i in range(M):
    for j in range(N):
        if visited[i][j]: continue
        target = graph[i][j]
        num = 1
        dfs(i, j)
        dic[target] += num**2

for value in dic.values():
    print(value, end = " ")