Python

[python3] 백준 1389 풀이 ( 케빈 베이컨의 6단계 법칙, 플로이드 워샬 )

이번 문제는 케빈 베이컨의 6단계 법칙이다. 케빈 베이컨이 할리우드의 핵 인싸라는 것을 인지하고 문제에 들어가자. 문제를 보자 문제가 상당히 길다. 읽어보면 그냥 네트워크 안에서 여러 사람들과 연결되어 있을때 모든 타인과 몇번만에 연결되어 있는지를 알아내어 최솟값을 가지는 즉, 허브 역할을 하는 사람을 구하면 된다. 문제를 잘 읽어보면 결국 N정점에서 N정점으로의 갈 때 얼마나 걸리는지를 구해야 한다. 그래야 한 노드에서 모든 노드에 방문할 때 케빈 베이컨의 수를 구할 수 있다. 즉, 모든 쌍 최단 거리 알고리즘을 사용하면 구할 수 있다. 모든 쌍 최단 거리 알고리즘의 대표적인 놈이 "플로이드 워샬"이다. 그러나! 플로이드 워샬은 O(N^3)이 걸리기 때문에 N값이 너무 크면 문제가 발생할 수 있다. 다..

백준 1707 python 풀이 (이분 그래프, BFS)

일단 처음에 문제를 읽고는 생각보다 쉽다고 느꼈다. 단순히 BFS로 탐색하면서 이전 값이랑 비교하면 되겠구만 했다. 그런데 구현하는데 상당히 애를 먹었고, 시간초과가 떠서 오랜 삽질 중이다. 우선 시간초과 코드는 아래와 같다. from collections import deque import sys input = sys.stdin.readline T = int(input()) def BFS(v,e,color, d,q): color[q[0]] = 1 visited = [0 for i in range(v+1)] while q: target = q.popleft() visited[target] = 1 targets = d[target] for t in targets: if visited[t] == 0: q.a..

백준 7576 토마토 (BFS, 행렬 그래프, python)

이번 문제는 원리도 파악하고 간단히 풀수 있다고 생각하고 코딩을 진행했다. 모든 예를 통과하고 반례도 통과하며 잘 코딩했다고 생각했으나 시간초과의 벽을 넘지 못하고 고수들의 코드를 보게 되었다. 원리는 어렵지 않다. 1. 토마토가 존재하는 곳을 찾아서 큐에 넣어준다. 2. 큐에서 하나씩 꺼내며 너비탐색을 진행한다. 3. 탐색이 끝나면 익지 않은 토마토가 존재하는지 확인한다. 4. 전부 익었다면 걸린 날짜를 출력, 익지 않은게 있다면 -1을 출력한다. 이를 토대로 코딩을 진행했다. 그러나 아래의 코드는 시간초과로 쓸수가 없었다. from collections import deque m,n = map(int, input().split()) L = [] for _ in range(n): tmp = list(m..

백준 2447 풀이 (재귀함수, 별찍기 - 10)

진짜 나한테 너무너무너무 어려웠다. 거의 포기하고 넘어갈까 고민하다가 유튜브로 재귀함수도 찾아보고, 알고리즘에 이끌려 포인터가 어려운가요 재귀함수가 어려운가요 동영상까지 보게됐다. 역시 문과생에게 알고리즘은 벽인건가 싶다가 그냥 코드를 외워버리기로 했고 코드를 외우다보니 어떤 방식으로 알고리즘이 진행되는지 이해가 됐다. 그래서 고수들의 코드를 토대로 내 코드를 다시 작성했다. def recur(num): global Map if num == 3 : Map[0][:3] = Map[2][:3] = [1]*3 Map[1][:3] = [1,0,1] return a = num//3 recur(num//3) for i in range(3):# 행 for j in range(3): #열 if i==1 and j==1..