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/2234 문제조건 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다.이 성에 있는 방의 개수가장 넓은 방의 넓이하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 각각 구하시오접근방법 전체 맵을 탐색한다는 점에서 BFS를 떠올릴 수 있었고, 1(2^0), 2(2^1), 4(2^2), 8(2^3) 로 진행할수 있는지 판단해야한다는 점에서 나에겐 조금 생소한 비트마스킹이 생각났다. 이 문제에서 핵심은 비트를 1부터 왼쪽으로 Shift연산을 통해 벽에 대해 나타낸 숫자와 &연산으로 겹치는 지..

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/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제조건 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우, 반..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제조건 벽(1)을 무조건 3개를 세운다. 벽은 바이러스(2)가 퍼져 나가는걸 막아준다. 안전영역(0)의 크기가 최댓값은 얼마인가? 접근방법 애초에 입력이 8이하로 너무 작아서 진짜 내 맘대로 구현할 수 있는 문제였다. 처음에는 최대한 깔끔하게 로직을 짤 수 없을까란 생각이 계속 들었지만, 그리디도 아니고, 어느 알고리즘도 적용할 수 없었다. 여기에 시간을 좀 많이 쏟은것 같다. 단순하게 문제조건만 맞춘다면 ..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제조건 N x M 크기의 보드가있다. 빨간공과, 파란공이 각 하나씩 있다.(위치 주어짐) 공을 내보낼수있는 구멍이 하나 있다.(위치 주어짐) 보드를 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 이 동작만으로 공을 움직여서 빨간공만 구멍으로 빼야한다. 빨간공, 파란공은 항상 같이..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제조건 (1,1) 에서 (n,m)까지 최단경로 벽을 하나까지 부술수있다. 조건 2 때문에 일반적인 bfs로 풀수가 없다. 벽은 부숴도 되고, 안부숴도되고 그렇다면 어떻게 하지,,? 생각을 해보면 bfs자체가 수행될때마다 최단거리를 의미하고, 그에따라 queue에 넣을 조건만 추가해주면 된다. 벽은 하나까지 부술수있으므로, 배열을 3차원배열로 만들어주고, queue에도 (..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제조건 목표지점부터 모든 지점에 대해서 목표지점까지의 거리 구하기 너무 당연하게 BFS로 풀이를 시작했다. #include #include using namespace std; int n, m, map[1001][1001], visited[1001][1001], dist[1001][1001]; int dy[] = { -1, 0, 1, 0 }; int ..