mojo's Blog

문제 링크 => 6087번: 레이저 통신 (acmicpc.net) 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS 문제이다. 사실 이런 유형의 문제는 몇번 풀어봤지만 아직도 부등호를 정확하게 어떻게 잡아야 할지에 대해서는 여러번 디버깅을 통해서 찾고는 한다. int 타입의 check 배열을 선언함으로써 해당 위치에 대한 거울을 놓을 수 있는 최소 갯수를 판단하기 위한 용도가 필요하다. 또한 이전에 어떠한 거울로 인해서 가르키는 방향에 대한 정보도 필요하다. 시작 지점부터 끝 지점까지 BFS 를..

문제 링크 => 1922번: 네트워크 연결 (acmicpc.net) 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리 문제이다. 간선에 대한 정렬은 merge Sort를 이용하였다. 그리고 Union-Find 알고리즘을 이용하여 Cycle이 발생하지 않도록 확인해주었다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include struct Edge { int from, to, dist; }; int parent[100001]; int N, M, cnt; Edge E[100001], tmp[100001]; void mergeSort(int le..

문제 링크 => 1916번: 최소비용 구하기 (acmicpc.net) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 연습 문제이다. 전부 c로 구현하면 좋겠지만 priority_queue는 귀찮아서 stl로 가져와서 써먹었다. 만약에 priority_queue를 구현한다면 알고리즘 시간에 배웠던 heap을 이용하여 조건을 더 추가하여 만들면 된다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #..

문제 링크 => 16946번: 벽 부수고 이동하기 4 (acmicpc.net) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 그래프 탐색을 이용한 문제이다. 먼저 이동할 수 있는 지점(0으로 구성된 곳)에 대해서 값을 먼저 세팅하도록 하였다. 문제에 있는 예시 2로 설명하자면 다음과 같다. 4 5 11001 00111 01010 10101 이때, 1은 이동할 수 없는 지점(벽)이므로 0으로 세팅하고 0으로 된 지점에서 그 다음 0으로 이동할 수 있는지를 파악하도록 한다. --- dp[N]..

문제 링크 => https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 트리 문제이다. 이 문제의 핵심은 정점 2개가 주어질 때 방향이 존재하지 않는다는 것이다. 즉, a b 가 입력되면 a => b 가 될 수 있고, b => a 가 될 수 있다는 소리다. 따라서 이를 고려해서 코드를 작성해야 한다. (이부분을 몰라서 계속 틀렸다.) 임의의 정점들의 간선으로 이어진 그래프에 대해서 Cycle 이 존재하면 해당 그래프를 무시하도록 하고..

문제 링크 => 17412번: 도시 왕복하기 1 (acmicpc.net) 17412번: 도시 왕복하기 1 첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다. www.acmicpc.net 최대 유량을 이용하는 문제이다. 이 문제에서는 이전에 풀었던 최대 유량 문제와는 다르게 from에서 to로만 가는 단방향으로 연결되어 있다는 것이다. 따라서 2차원 배열 capacity를 채우는 과정은 c[from][to] = 1 만 해주면 끝이다. (from => to가 중복해서 나타나는 일이 없으므로 +는 하지 않음) 세팅이 끝나면 Edmond carp Algorithm 을 이용..