https://www.acmicpc.net/problem/1348문제조건R x C 모양의 주차장N개의 차와, M개의 주차 구역차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.한 칸에 여러 대의 차가 동시에 들어갈 수 있다. 모든 차가 주차하는데 걸리는 시간의 최솟값을 구하시오.접근방법 단순하게 BFS를 이용해서 탐색하면 되는 문젠줄 알았는데, 전혀 그렇게 풀리지 않는다. 일반적인 구현문제가 아니라 특수한 알고리즘이 필요한 문제다,,,  Bipartite matching 이분매칭이라는 알고리즘이 필요하다. 주차구역과 차를 연결해주면서 짝을짓고, 짝을 짓는 경우의 수에 따라 최솟값을 비..

https://www.acmicpc.net/problem/2152문제조건  총 M(1 ≤ M ≤ 100,000)개의 비행로가 존재각각의 비행로는 한 방향으로의 서비스만을 제공S(1 ≤ S ≤ N)번 도시에서 시작해서 T(1 ≤ T ≤ N)번 도시에서 여행을 끝냄  최대로 방문할 수 있는 도시의 개수 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다.접근방법 문제를 읽고 나서 든 생각은 띠용(?) 이게 뭐야,,, 였다,,문제 조건중 몇 번이든 같은 도시를 방문할 수 있다는 점을 이해하기가 어려웠다.그리고 같은 항공로를 여러 번 이용한다는 말에서 조금 감이왔다. "이거 순환이 될수 있으니까 뭔가 묶어볼수 있지않을까?"우연치 않게 학교 강의에서 들었던 SCC(S..

https://www.acmicpc.net/problem/16946 문제조건N×M의 행렬로 표현되는 맵0 : 이동가능, 1 : 벽각각의 벽에대해 해당 벽을 부수고, 이동가능한 장소로 바꾼뒤 그 위치에서 이동가능한 칸의 개수접근방법 처음에는 정말 단순하게 모든 벽에 대해서 BFS를 돌렸다가 시간초과가 났다.최악의 경우 1000^3 이면 10억인데,, 대략 10초가량 소요되는 것이다.그래서 어떻게 하면 시간을 줄여가며 해결할까 고민 한 결과,,, visited 배열을 각각 벽에대해 초기화 시켜주는 작업을 안해주면 시간제한에 안걸릴것이라고 생각했다. 그래서 벽을 탐색하는 것이아니라, 맵에서 이동가능한 부분인 0인 값에서 부터 BFS를 진행해서 인접한 벽에 누적으로 값을 더하고, visited배열을 초기화해줄 ..

https://www.acmicpc.net/problem/2580 문제조건스도쿠판을 채우자각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.접근방법 문제를 보자마자 떠오른 생각은 N-Queen 문제와 상당히 유사한 문제라는 생각 이었다. 물론 Brute Force로 모든 경우의 수를 탐색해서 구할 수도 있겠지만, O(2^n) 이상의 시간소요로 시간초과가 날 것이 분명했고, N-Queen문제와 같이 백트래킹으로 접근했다.유망한지 판단하고, 유망하다면 DFS를 진행하는 백트래킹 방식에서 시간단축이 됨을 인지하고, 가로, 세로, 3x3 크기의 칸에서 같은 숫자가 하나도 없는지 체크하고 그..

https://www.acmicpc.net/problem/17136 문제조건  1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이가 있다.각 종류마다 5개씩 가지고 있다. 10×10인 종이에 색종이를 붙인다. 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다., 0이 적힌 칸에는 색종이가 있으면 안 된다. 필요한 색종이의 최소의 개수?모두 덮는것이 불가능한 경우 -1을 출력 접근방법 하나씩 범위를 넓혀주는 BFS 방법을 써야하나,,? 라는 생각이 들었지만 정형화 시킬 방법이 떠오르지 않았다. 따라서 DFS측면으로 접근했는데, 한변의 길이가 1일때부터 5일때 까지 하나씩 판단해야하고, 그럴려면 중복을 방지 하기위해 visited 배열을 활용해야한다. 이 ..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제조건 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있다. 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 숫자를 최대로 뽑는 경우, 뽑는 숫자들을 출력하라. 접근방법 모든 경우의 수를 따져서 비교해줄려고 DF..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제조건 부모 자식들간의 관계가 주어졌을때, 계산하고자 하는 두사람의 촌수를 구해라 접근방법 트리 모양 구조를 탐색하는 그래프 탐색 방법으로 접근했다. 근데 촌수 이므로 cycle이 생길 일은 없다. 따라서 각 노드를 양방향 연결해주고 DFS로 탐색해줬다. 아버지의 형제들과 나와의 관계는 3촌으로 분류할 수 있는데, 이를 계산하는 방식은 나 → 아버지(1촌) → 할아버지(2촌)..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제조건 톱니바퀴 4개, S극(1), N극(0) 존재 각 톱니바퀴가 맞닿아있는 부분이 극이 다르면 다른 방향으로 회전, 같으면 맞닿아있는 톱니바퀴는 회전X 12시방향부터 시계방향순서대로 8개의 톱니에 S, N 주어짐 돌리는 과정을 모두 수행한뒤, 최종적인 톱니바퀴 상태에서 4개의 12시방향에 있는 S들의 합 문제 파악하는데 30분 정도 걸린거같다. 역시나 문제는 복잡하고 풀이 방법은 쉽겠지,,..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제조건 n명의 사람을 각각 n/2 명씩 두팀으로 나눈다. 한 팀의 능력치는 (i, j) 가 같은 팀이라면 map[i][j] + map[j][i]로 나타내고, 같은 팀의 사람들의 능력치를 모두더한다. 두 팀의 능력치 차이의 최솟값은? 접근방법 보자마자 입력값도 작고, 최솟값을 구하기 위해 모든 경우의 수를 Brute Force로 탐색하면 되는 거 아닌가? 생각이 들었고, DFS로 모든 경우의 수에 대해서 탐색했다. 너..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제조건 n x n 크기의 대나무숲 어디든지 판다를 풀어놓을수 있다. 판다는 대나무를 다먹으면 상, 하, 좌, 우 중 한지역으로 이동한다. 이동하는 칸의 대나무가 원래있던 칸의 대나무 수보다 많아야 이동한다. 가장 많이 이동하는 경우의 이동수는? 접근방법 문제를 보자마자 생각이 들었다. '아 그냥 완전탐색돌려서 최댓값 갱신해서 찾자' 내가 좋아하는 DFS 알고리즘으로 모든 경우의 수를 ..