1. 문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 2. 풀이 BFS + 비트마스킹으로 해결하는 문제. 좌표 평면에서 BFS 혹은 DFS의 이동을 생각할 때, 흔히 방문한 곳을 다시 방문하지 않기 위해 boolean OR Int형으로 2차원 방문 처리 배열을 만들어 처리한다. 그러나 이 경우는 조건을 가지지 않고 이동하는 경우에는 편리하나, 조건을 가지고 이동하는 경우에는 따로 조건 처리를 해주거나 그리디한..
1. 문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이 외판원(TSP)의 기본 문제 중 하나이다. 노드의 개수 $O(x^n)$ 주요 자료구조 1. int[][] inMatrix : 인접 행렬 2. boolean[] nodeVisited : 노드 방문 처리 배열 입력으로 주어지는 값으로 인접 행렬을 구성한다. 이 문제의 포인트는 최소 값을 가지는 경로는 하나이기 때문에 모든 정점에서 DF..
1. 문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 2. 풀이 백준 2638 치즈 문제와 거의 똑같은 문제(https://www.acmicpc.net/problem/2638) 이 문제의 핵심 또한 가장 자리에는 치즈가 무조건 없으므로, 치즈가 없는 공간(공기 공간)이 외부 공기인지 내부 공기인지 파악하는 것이 중요하다. 주요 변수 및 자료구조 1. Queue pointQueue : 녹을 치즈의 좌표를 저장할 Queue 2. int cnt : while문을 ..
1. 문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 2. 풀이 배열의 모든 부분 집합을 구하여 값을 계산한다면, 배열 하나만 해도 시간 복잡도 $ O(2^n) $를 가지기 때문에 시간초과가 발생한다. 이 문제의 핵심 포인트는 "누적합"을 구하는 것이다. 그렇다면 A 배열과 B 배열의 누적합의 개수는 몇 개씩이 나올까?? A 배열에서 누적합의 개수는 총 n개가..
1. 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 2. 풀이 문제에서 핵심으로 생각한 부분은 "특정 건물을 짓고 다음 건물을 지을 수 있다" 부분이다. 이는 위상정렬의 "특정 과목을 수강한 후에 다른 과목을 수강할 수 있다"와 같다고 볼 수 있다. 기본적인 위상정렬과 같은 로직으로 돌아가지만 조금 다른 부분이 있다. 바로 건물을 짓는 시간에 대한 부분이다. 문제의 그림에도 나와 있는 예제 입력 1번을 보면, 1번 건물과 연결된 2..
1. 문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 2. 풀이 단순 DFS로 문제 해결 시 시간초과 발생 풀이 Point는 DFS + DP로 DP를 이용하여 다음에 탐색하려는 위치의 DP 값이 지금 현재 Depth보다 크다면 그 부분으로는 탐색을 하지 않는 것이다. 그리고 동전을 무한번 움직일 수 있다는 것은 사이클이 발생할 수 있다는 것이므로 4방 탐색을 체크하면서 방문했던 지점을 또 방문할 수 있다면 이는 사이클이 발생할 수 있다는 ..
1. 문제 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 2. 풀이 하나의 비행기는 1~자기 자신까지의 게이트에 도킹할 수 있지만, 최대한 많은 비행기를 도킹하기 위해선 주어진 수 범위의 수 중 최대한 큰 수의 게이트에 도킹해야 한다. 게이트 수 G가 최대 10 ^ 5개, 비행기의 수가 최대 10 ^ 5개이므로 단순 반복문(O(n^2))으로는 해결할 수 없다. 제한시간인 1초에 맞추기 위해선 log N의 시간..
1. 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2. 풀이 문제에서 A 다음에 B가 나올 경우 A가 B보다 앞에 있어야 하므로 인접 리스트로 생각한다면 A 노드 다음에 B노드가 연결되어 있다고 생각할 수 있다. 그리고 1 3 이 주어졌을 때 3 1이 또 주어지는 경우는 없으므로 한 방향으로만 흐른다. 노드 다음 특정 노드를 연결하고 이를 순서대로 출력해야 하므로 위상 정렬을 생각할 수 있다...
