개인사

리뷰노드를 1 ~ N 까지 설정해 줘야 했는데, 0 ~ N - 1까지로 설정해 주고 있었어서 계속 틀렸다.. 근데 왜 예제랑 82% 까지 맞는거지? 문제 풀이도시의 최대 개수는 200개 이므로 nodes 배열을 201의 크기로 초기화 해준다.2중 for문을 통해 인접행렬에 있는 값을 받아오고 1이 입력된 경우 해당 row와 col을 참조하여 Union 처리 해준다, 이때 유니온 파인드를 사용하므로 양방향 간선은 의미 없기에 대각선으로 갈라 싸이클 없이 한쪽 면만 받아와도 된다.이후 쿼리로 오는 노드들을 Find를 통해 루트 노드가 같은지 비교하고 만약 다르다면 break 후 NO를 출력한다. 당연히 break 되지 않았다면 YES를 출력하면 된다. 참고 사항대부분의 문제에서 0번 노드를 주는 경우는 없기..

리뷰유니온 파인드의 기초적인 문제 문제 풀이노드는 최대 100만개 까지 입력받을 수 있으므로 nodes 배열을 1000001 크기로 초기화 해준다.이후 각 노드에 자기 자신을 value로 받도록 값을 입력해 준다.이후 쿼리를 입력받아 a가 0일 경우 b와 c를 Union 함수의 인자로 보내고, a가 1일 경우 Find 함수의 인자로 보낸다.Union은 입력받은 두 노드를 Find를 통해 루트 노드를 받아온 뒤 만약 두 노드의 루트가 같다면 return 아닐 경우 뒤 노드의 루트를 앞 노드의 루트로 바꾸어 준다.Find는 루트 노드를 찾을 때 까지 재귀를 통해 노드를 탐색해 준다. 이때 재귀를 빠져나오며 경로에 있는 노드의 value를 루트 노드로 갱신해 준다.만약 a가 1일때 b와 c를 Find한 값이 ..

개요1. 그래프와 트리의 차이점트리는 무방향 간선을 가지며 사이클이 없고 특정 노드 간 경로가 유일한 그래프다.그래프 내에는 여러개의 신장 트리가 있을 수 있다. 2. 신장 트리 (Spanning tree)N개의 노드를 N - 1개의 간선으로 모든 노드가 연결된 트리 3. 최소 신장 트리 MST가중치가 최소인 신장 트리 = Minimum Spanning Tree간선에 가중치가 주어졌을때 간선의 합이 최소인 Spanning Tree가 최소 신장 트리가 된다.  아래와 같은 간선간 가중치가 있는 그래프가 있다고 가정 해보자노드의 개수는 9개이므로 8개의 간선으로 9개의 노드를 모두 이을 수 있는 가중치의 최소값은 얼마일까? 각 가중치가 오른쪽과 같은 간선을 선택하여 더하면 20 + 21 + 1 + 13 + ..

개요Union-Find데이터 단위를 그룹단위로 나누어 관리하는 알고리즘 Union으로 그룹을 합치고, Find로 찾는 구조이다.중간에 어떤 노드가 있는지 전혀 궁금하지 않고, 그룹을 합치고, 특정 노드가 어떤 그룹에 속해 있는지 파악하는 것에 초점이 맞혀져 있다.교집합이 없는 서로소 집합(disjoint set), 그룹을 합치는 것은 있으나 그룹을 쪼개는 것은 없다. Union일정 노드들을 그룹으로 묶고 부모 노드가 대표가 된다.Union(1, 2), Union(3, 4), Union(5, 6)위와 같이 묶은 경우 각 묶음은 하나의 그룹이 된다. Find단순하게 해당 노드를 찾으라는 의미가 아닌, 해당 노드가 속한 그룹을 찾는다. 1. 초기 단계모든 노드들이 대표인 상태  노드123456부모123456 ..

리뷰각 테스트 케이스마다 맵을 초기화 해주어야 하는데 해당 부분을 까먹어 OutOfBounds 에러가 노출되었다. 문제 풀이2차원 string 배열을 초기화 해준다. l * r 크기로 초기화 해준 뒤 문자열을 입력 받는다.문자열의 각 요소를 훑고 만약 S를 찾았다면 시작 위치 좌표로, E를 찾았다면 종료 위치 좌표로 저장해 준다. 이후 빈 칸 '.'로 초기화를 해준다.bfs를 실행해 준 뒤 1개의 방향, 상하좌우 및 위층과 아래층의 방향으로 탐색을 해준다.while 루프가 종료되기 전 목적지에 도착한 경우 해당 시간을 리턴, while루프가 종료된 경우 -1 을 리턴해 준다.bfs 결과가 -1을 리턴한 경우 Trapped!을 출력, 아닌 경우 Escaped in (리턴 값) minute(s).을 출력해 ..

리뷰다익스트라를 활용하되 최단 경로까지의 시간이 아닌, 최단 경로 중 가장 먼저 밟아야 하는 노드를 출력하는 문제 문제 풀이인접리스트를 n + 1크기로 초기화 해주고 가중치와 시작, 도착 노드를 양방향으로 추가해 준다.이제 각 노드에 대해 해당 노드를 시작점으로 하는 다익스트라를 돌려주면 된다.거리를 나타낼 dist 벡터를 n + 1 크기, 기본값을 10억으로 초기화 해주었다.경로를 나타낼 path 벡터를 n + 1 크기로 초기화 해주었다.최소 힙을 정의해 주고 거리를 0으로 시작 노드를 추가해 준뒤 시작 노드의 거리를 0으로 초기화 해준다.이후 일반적인 다익스트라 로직을 실행 하되, 경로가 갱신되었을 경우 path 벡터를 변경해 준다.만약 현재 노드의 path가 비어있을 경우 다음 노드의 경로에 다음 ..

리뷰특정 노드를 무조건 방문하고, 방문하지 않는 조건을 가진 최단 경로 문제 문제 풀이n, m을 입력 받고 인접 리스트를 n + 1 크기로 초기화 해준 뒤 단방향으로 노드와 가중치를 벡터에 넣어준다.x, y, z를 입력 받고 first에 x 에서 y까지의 최단 경로를 구하고, y부터 z까지의 최단 경로를 구한 뒤 더해준다.second에 x부터 z까지 최단 경로를 구해준다. 이때 bfs에 flag를 전달 해 y를 들릴지 말지를 정해준다.bfs가 실행되면 n + 1크기의 거리 배열을 매우 큰 값으로 초기화 해준 뒤 최소힙을 만들어 준다.시작 위치를 힙에 넣고, 거리를 0으로 초기화 해준 뒤 while 루프를 돌려준다.만약 bfs에 전달된 flag가 0이라면 기존 bfs를 진행, flag가 1이라면 다음 노드..

리뷰문제 정보가 좀 애매해서 정답 도출에 어려움을 겪었다, 그냥 다익스트라로 s 부터 t까지의 최단 경로를 구하면 된다. 문제 풀이n, m값을 입력 받고 인접 리스트를 n + 1 크기로, 거리 벡터를 n + 1, 값을 최대한 크게 설정해 준다.연결이란 두 정점이 간선을 통해 방문 가능하다고 문제에 쓰여있으니 양방향 이동이 가능하다.시작 노드와 목적지 노드를 입력 받고 시작 노드를 힙에 추가, 시작노드의 거리를 0으로 초기화 한다.while 루프를 시작해 시작 노드로 부터 각 노드까지의 최단 경로를 찾아 준다.이후 목적지 까지의 노드를 출력해 주면 된다. 참고 사항특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 ..

리뷰너비우선 탐색을 통하여 해결하는 문제, 최단 거리를 출력하고 그 경로도 기억해 주고 있다가 출력해 줘야 한다. 문제 풀이n과 k값을 입력 받고 만약 n가 k보다 클 경우 n - k와 n에서 k까지의 정수를 모두 출력해 준다.아닐 경우 bfs를 실행해 주고 큐에 정수와 경로를 저장할 pair나 구조체를 활용해 준다.최단 경로는 방문 배열을 방문하지 않은 곳은 0, 방문할 곳은 현재 이동 횟수 + 1로 해주면 된다.경로를 벡터에 추가해 주고 큐에 푸시한 후에는 꼭 pop_back을 해줘야 다음 for문 탐사에 문제가 없다.목적지에 도달한 경우 방문배열의 k인덱스를 출력, 벡터에 들어있는 경로들을 공백을 두고 출력해 준다. 참고 사항테스트 케이스1 100000211 2 3 6 12 24 48 49 98 1..

리뷰실버 1문제에서 왜 틀렸나.. 고민했는데 부등호 하나 빼먹은게 원인이었다. BFS로 풀긴 했는데 for문을 세번 사용하는 플로이드-워셜로도 풀 수 있다고 한다. 문제 풀이n값을 입력 받고 인접리스트를 n + 1 크기로 초기화 해준다.m값을 입력 받고 m줄에 걸쳐 입력되는 두개의 노드를 쌍방향으로 연결 해준다.각 노드별 케빈 베이컨 숫자를 받아올 벡터 kb를 n + 1 크기로 초기화 해준 후 브루트포스로 bfs를 돌려준다.bfs 내에서 방문 배열을 0으로 초기화, 현재 노드를 방문처리, 다른 노드에 방문 할때마다 ct를 1 올려주고 cnt에 ct를 더해준다. 만약 cnt가 여태까지의 최소 cnt보다 클 경우 바로 return 해줘도 된다.모든 노드에 대해 bfs가 종료된 후 가장 적은 케빈 베이컨 숫자..