백준 (4) 썸네일형 리스트형 [백준 경로찾기] DFS 문제, 2차원 벡터 활용 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 경로찾기 문제로 문제를 푸는 알고리즘은 다음과 같다. 1) q.pop() 나온 노드를 현재노드로 지정 2) 현재노드에서 주변노드에 방문 안했으면 방문처리후, q.push() 이 문제는 매우 간단하나 시간초과를 막기위해 문제를 풀기위한 시스템을 마련하는 방법이 중요하다. 현재노드에서 주변노드를 탐색할 때, for문으로 주변 노드를 모두 다 확인하면서 연결되있는 여부를 검사한다면 노드가 100개존재할 때, 요구되는 시간이 매우 많아질것이다. .. [백준 ACM craft] 위상정렬 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net ACM craft라고 starcraft 문제를 비유한 듯한 문제다. 위상정렬문제이지만 단순 위상정렬문제가 아니라 각각의 건물이 지어.. 백준 구슬탈출2 https://www.acmicpc.net/problem/13460 최단경로를 찾는 문제는 BFS로 구현해야한다. 그런데 이 문제에서 BFS로 구현하면서 각각의 노드에 대해서 기억해야 하는 정보가 많아서 난항을 겪었다. BFS를 큐를 이용해서 구현하려고 했기 때문인데 생각해보니 큐에 기본 자료형을 넣을 생각만 하고 있었기 때문이다. BFS에 쓰는 큐에 들어가는 자료형을 구조체로 직접 선언하여 필요한 정보를 각각의 노드마다 전부 저장하였다. 다음과 같이 저장했다. BFS를 구현하는데 있어서 자기 마음껏, 재량껏 소스를 구현함에 따라 구현이 가능할 수도 있고 못할 수도 있었다. 전체 해답 소스는 다음과 같다. #include #include #define LEFT 0 #define DOWN 1.. 백준 공유기설치 https://www.acmicpc.net/problem/2110 백준 공유기설치 문제이다. 이진탐색 문제인데 꽤나 신박한 문제였다. 문제를 본 순간 드는 생각은 공유기를 하나하나씩 둬 보면서 경우의 수를 따져보는 것이었다. 다시 말해서 완전탐색으로 풀 수 있는 문제지만 역시 백준문제답게 시간제한이 있으므로 완전탐색보다 빠른 이진탐색을 이용하면 풀 수 있을거라 생각했다. 공유기설치하는 집 사이의 최소거리를 이진탐색으로 찾는것을 생각하는 것이 꽤나 어려웠다. 해결 알고리즘 1. 이진탐색으로 nCurDst를 설정한다. 2. 설정한 nCurDst로 공유기를 다 설치할 수 있는지 확인한다. (CheckDistance()) 3. 공유기를 설치할 수 있으면 더 큰 nCurDst로 다시 탐색하고 해당 nCurDst를.. 이전 1 다음
