Problem Solving/그래프 썸네일형 리스트형 BOJ 4792 - 레드 블루 스패닝 트리 문제 링크(Link)https://www.acmicpc.net/problem/4792 문제 해결(Solution) MST를 두 번 생성해서 문제를 해결할 수 있다. 1. min_blue : R 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수 2. max_blue : B 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수 3. Answer : min_blue 더보기 BOJ 11559 - Puyo Puyo 문제 링크(Link)https://www.acmicpc.net/problem/11559 문제 해결(Solution) 1. 기본적인 BFS or DFS와 구현을 물어보는 문제. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 몇 번 블럭이 삭제되는 지를 물어보는 문제가 아니고 몇 번 연쇄되는 지를 물어보는 문제임을 숙지해야한다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1761 - 정점들의 거리 문제 링크(Link)https://www.acmicpc.net/problem/1761 문제 해결 (Solution) 1. 문제에서 주어지는 그래프가 트리(Tree)임을 알고있다. 2. 트리에서 두 정점의 거리를 일반적인 방법으로 구하기 위해선 시간복잡도 O(N)이 소요된다. 쿼리의 개수를 고려하면 전체 시간복잡도는 O(NM)이 소요된다. 즉, 400,000,000(4억) 이므로 시간 초과에서 자유로울 수 없다. 3. dp를 이용한 LCA(최소 공통 조상) 알고리즘을 이용하면 O(logN)만에 두 정점의 거리를 구할 수 있다.(트리에서만...) 4. dp[i][j] = 정점 i에서의 2^j 번째 조상. 5. dist (dist[i] = 루트에서 부터 정점 i 까지의 거리) 라는 배열을 활용해서 두 정점사이.. 더보기 SW Expert Academy 1795 - 인수의 생일 파티 문제 링크 - 문제 해결 1. 단방향 그래프를 입력받고, 1부터 N까지의 임의의 점에서 K까지의 최단거리와 K부터 임의의 점까지의 최단거리의 합 중에서 가장 큰 값을 구하는 문제. 2. 다익스트라 알고리즘으로 문제 해결. 주의할 점 || 생각해볼 점 1. 최대 간선의 수(N)가 10,000개, 최대 정점의 수(M)가 1,000개. 1부터 N까지의 임의의 수 전부에서 최단거리를 구하려면 시간복잡도 에 의해서 아슬아슬해진다. 그러므로 입력 받을 때, 정방향과 반대방향 인접리스트를 두 개 만들어서 K에서 다익스트라 알고리즘을 두 번 수행하면 된다. 참고 - 다익스트라 알고리즘 visual code : https://www.swexpertacademy.com/main/visualcode/main.do#/home.. 더보기 codeground practice - 최소 신장 트리 문제 링크로그인을 해야만 볼 수 있다. 문제 해결 1. 신장 트리를 만들되, 선택된 간선들의 중간 값이 가장 최소가 되는 신장 트리를 만들어야한다. 말이 복잡하지만 결국은 MST를 구하는 문제다. 왜냐면 간선들의 중간 값은 가중치가 작은 간선들이 많을 수록 작아지기 때문이다. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 14502 - 연구소 문제 링크https://www.acmicpc.net/problem/14502 문제 해결 1. DFS를 이용해서 문제 해결. 0과 2의 row, column 인덱스를 저장하고 3중 for문을 활용해서 문제 해결. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 14621 - 나만 안되는 연애 문제 링크https://www.acmicpc.net/problem/14621 문제 해결 1. "모든 정점이 연결되어야한다", "도로의 합이 최소가 되어야한다" → 최소신장트리(MST) 문제를 크루스칼 알고리즘(Kruskal Algorithm)으로 해결 주의할 점 || 생각해볼 점 1. 최소 경로를 해결하는 Dijkstra 알고리즘을 사용할 수 없다. 실제 정점끼리의 최소 거리랑 신장된 트리에서의 거리는 다를 수 있다. 2. 이분 그래프로 해결하려면 까다롭다. 그래서 정점마다 W or M 을 저장해서 서로 같다면 연결에서 제외했다. 3. 만약 모든 정점이 연결되지 않으면 -1을 출력하는 것을 잊으면 안된다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 1884 - 고속도로 문제 링크https://www.acmicpc.net/problem/1884 문제 해결 1. 다익스트라에서 돈이라는 개념이 들어간 문제. 주의할 점 || 생각해볼 점 1. dist[i][j] : 정점 i 에서 j만큼 돈을 소모한 상태일 때의 거리. (원래 다익스트라에선 일차원 배열로 선언한다.) 2. 정점 N을 만나면 바로 종료한다. ① 정점 N에서 바로 종료하지 않았을 때. ② 정점 N에서 바로 종료했을 때 시간과 메모리 모두 확연하게 줄어든다. 참고 - KCM Travel (이 문제와 비슷하다) : https://www.acmicpc.net/problem/10217 ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 5558 - 치 ~ 즈 문제 링크https://www.acmicpc.net/problem/5558 문제 해결 1. 최소 시간으로 치즈를 모두 먹어야한다. 상하좌우로 움직일 수 있으므로 BFS (넓이 우선 탐색)를 사용한다. 2. 번호 순서대로 치즈를 먹기 위해서 왔던 길도 되돌아가야하므로 BFS를 응용해야한다. 3. 한 번에 해결하기 보다는 (시작점 → 1번 치즈), (1번 치즈 → 2번 치즈), (2번 치즈 → 3번 치즈) ... 순으로 문제를 나눠서 해결하는 것이 좋다. 주의할 점 || 생각해볼 점 1. 방문했던 곳을 매번 false로 초기화시켜줘야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2526 - 싸이클 문제 링크https://www.acmicpc.net/problem/2668 문제 해결 1. 다음 정점 = (P로 나눈 나머지) * N % P; 2. 배열을 만들어서 numbering한 값을 넣어준다. 3. 만약 배열의 값이 0이 아니라면 사이클이 생긴 것이므로 그 때의 값과 사이클 시작의 값의 차를 출력한다. 주의할 점 || 생각해볼 점 1. P의 범위가 97 밖에 안되므로 사이클이 생기는 정점은 0 ~ 96 까지다. 2. 한 정점에서 나가는 간선은 무조건 하나라는 사실을 인지하면 더욱 수월하게 해결할 수 있다. 참고 - http://vjerksen.tistory.com/30 (사이클을 DFS로 해결) ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 2 다음
