Simple Explain

#1167번 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름을 구하는 문제이다. 대충 거리의 총합정도는 구하겠는데 어떻게 최대거리를 갖는 노드를 찾는지 도저히 이해가 되지 않았다. 다음 블로그를 참고했다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름..

저번 포스팅 중에서 0-1 BFS를 공부할 필요가 있다고 했었다. 근데 오늘 자연스럽게 해버림 #1261 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 처음엔 그냥 DP를 사용한 BFS로 풀이했다. N, M = map(int, input().split()) way = [[int(x) for x in input()] for _ in range(M)] visited = [[-1 for _ in range(N)] fo..

#14226번 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 일단 열심히 짰다. T = int(input()) dist = [-1]*(1000+1) # index = 이모티콘 개수 # value = 연산 횟수 def bfs(T): que = [1] dist[1] = 0 copy_data = 0 while que: c = que.pop(0) if c == T: return dist[c] # 이전에 복사한 값 붙여넣어 모든 값 만들기 if..

#13549 숨바꼭질3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 신기한 문제였다. BFS를 공부하다가 만난 문제이지만 사실 BFS를 통한 풀이가 온전한 풀이가 아니라는것. 문제는 점프라는 행위에 있다. 다른 행위와는 달리 점프에 소요되는 비용은 0이다. 그래프 내에서 가중치가 0이라는 말이다. 모든 엣지의 가중치가 동일할 때 정확한 수행능력을 보여주는게 BFS알고리즘이다. 그렇기 때문에 가중치가 다른 위..

#13913번 숨바꼭질4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 전에 풀었던 숨바꼭질 문제(https://www.acmicpc.net/problem/1697)에서 단순히 거리만을 저장하는게 아니라 경로를 저장하는 형태로 코드를 변경했다. N, T = map(int, input().split()) M = 10**5 dist = [[]]*(M+1) dist[N] = [N] def solve(positi..

#16964 DFS 스페셜 저지 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 처음 내가 구현했던 코드이다. import sys input = sys.stdin.readline N = int(input()) matrix = [[] for _ in range(N+1)] for i in range(N-1): prev, to = map(int, input().split()) matrix[prev].append(t..

#1697번 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 너무 쉬운 문제라 가볍게 임했다. N, T = map(int, input().split()) visited = [False]*(100001) que = [] def solve(time, position): visited[position] = True que.append([position, time]) while que: # prin..

#16940번 BFS 스페셜 저지 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 층별로 돌면서 그 층에 있는 노드들의 다음층 노드에 속하는지 판단하는 코드를 구현하고 싶었다. 하지만 맘처럼 잘 되지 않더라... N = int(input()) matrix = [[] for _ in range(N+1)] for i in range(N-1): prev, to = map(int, input().split()) matrix[prev].append(to) matrix[to].append(prev) matrix[0].append(1) target = list(map(in..

#16947번 서울 지하철 2호선 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 테스트케이스 통과까지는 성공했지만 시간초과가 났다. import sys sys.setrecursionlimit(10**9) N = int(input()) matrix = [[] for _ in range(N+1)] for i in range(N): prev, to = map(int, input().split()) matrix[prev]...

#16929번 Two Dots https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 무난하게 풀 수 있을거라 생각했다. N, M = map(int, input().split()) mat = [] attrs = set() for i in range(N): tmp = [] for j in input(): attrs.add(j) tmp.append(j) mat.append(tmp) def print_mat(mat): for i in mat: pr..