[Boj/백준] 6118 Python

문제출처: https://www.acmicpc.net/problem/6118

6118번: 숨바꼭질

 

1. 문제 접근 방식

문제를 이해하는데 살짝 시간이 걸렸다.

일단 2차원 DFS/BFS문제가 아닌 것을 확인했다.

그래프를 1,n+1까지 각 노드와 연결된 원소들을 나타내는 꼴로 만들었다.

BFS를 돌면서

total이라는 배열에 값을 1씩 더해줬다.

 

 

2. 내가 푼 코드

import sys
from collections import deque

def bfs(graph,visited):
    queue = deque([1])
    visited[1] = True
    total = [0]*(n+1)

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                total[i] = total[v]+1
                queue.append(i)
                visited[i] = True
    return total

n, m = map(int,sys.stdin.readline().split())

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


for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

result = bfs(graph,[False]*(n+1))

a = result.index(max(result))
b = result[a]
c = result.count(max(result))

print(a,b,c)

 

 

3. 결과 및 느낀점

우선 2차원 BFS문제가 아니라 1차원 BFS 문제일 경우에 visited배열을 사용하기 마련인데

visited 배열과 graph 배열은 무조건 매 함수 호출마다 인자에 넣는 방식을 사용해서 초기화 시켜주자

그리고 ~의 합을 구하는 문제면

bfs 함수안에 total처럼 배열을 만들어서 i in graph[v]일 때 total[i]에 이전 값+1과 같은 연산을 시켜주자.

비슷한 문제는 비슷하게 빨리 푸는 것이 중요할 것 같다. ex)boj1389