https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 1. Logic 처음에 DP로 될거같아서 시도했는데 DP는 vis배열을 찍고 나오기 때문에 최단거리 계산이 안된다. 그리고 vis배열을 기록을 안하게 되면 루프를 계속 들어가기 때문에 힙이 터진다..ㅋㅋㅋㅋ 결국 BFS 느낌으로 해결 이 문제에서 " 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다."는 배수만큼 앞으로 이동 + 배수만큼 뒤로 이동할 수 있다. 2...
백준
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. Logic 입력을 인덱스로도 받지만 string으로 받은 후 0의 위치를 찾고 그 상태에서 옮길 수 있는 좌표를 찾아 BFS 브루트포싱한다. 방문처리를 어떻게 해야 할 지 고민이었는데 map / set을 활용하여 중복이 되지 않도록 처리해줬다. map을 활용한 풀이, set을 활용한 풀이 둘 다 해봤다 2. Code map을 활용한 풀이 #include using namespace std; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. Logic 정사각형이 같은 섬에 잇는 조건은 가로, 세로, 대각선으로 걸어서 갈 수 있는 경로가 있어야 한다. 즉 8방향 탐색을 해서 섬의 갯수를 구해주면 된다. 2. Code #include using namespace std; int graph[51][51]; bool vis[51][51]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[8] ..
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 1. Logic 여기서 주의해야 할 점은 바이러스가 퍼지면서 비활성 바이러스에 닿게 되면 그 부분은 시간으로 처리를 안해준다. 문제에 따로 명시는 되어있지 않지만 테스트 케이스를 설명해주는 그림을 잘 보면 그렇게 되어있다... 1. 문제를 푸는 로직은 먼저 입력받으면서 바이러스가 있는 좌표를 저장해놓는다. 2. 바이러스를 활성화 할 수 있는 갯수가 정해져있기 때문에 조합을 활용해서 m개만큼 활성화 할 바..
https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 1. Logic 다른 분들의 풀이를 본 결과 내가 푼 방식인 위치마다 주위의 쓰레기 여부를 판단하는 방법이 있고 먼저 쓰레기 여부를 판단하여 배열에 넣은 후 다익스트라를 돌리는 방법 이렇게 2가지가 가장 대표적인 풀이인 것 같다. 내가 푼 방식인 위치를 옮길 때 마다 쓰레기 여부를 판단하는 방법은 1. 입력을 받고 시작, 도착 위치를 기록 후 2. 다익스트라를 실행 하..
https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 1. Logic 시작점에서 출발해서 다른 정점들을 거쳐 n-1번째 노드에 도착 하는 최단 거리를 구해야 하기 때문에 다익스트라를 사용해서 풀었다. 와드나 시야가 있는지를 체크하기 위해 bool sight배열을 선언 후 sight배열이 true면 continue하도록 조건을 넣어준 후 다익스트라를 돌리면 된다. 2. Code #include using namespace s..
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. Logic 시작점에서 시작하여 모든 노드를 순회하면서 연결된 모든 노드까지의 최단거리를 갱신한다. 한 노드에서 모든 노드까지의 최단거리를 구하는 문제이기 때문에 다익스트라 알고리즘을 사용했다. 2. Code #include using namespace std; const int INF = 0x3f3f3f3f; int n..
https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 1. Logic vis배열을 선언하여 탐색한 곳을 표시한다. -모양을 만나면 가로로 끝까지 탐색하며 vis배열에 기록한다. |모양을 만나면 세로로 끝까지 탐색하며 vis배열에 기록하고 연산을 한 횟수를 세준다 2. Code #include using namespace std; string input[51]; bool vis[51][51]; int main() { int n, m; cin >> n >> m..
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 1. Logic 좌상우하 순서대로 1, 2, 4, 8이라는 값을 가지고 있기 때문에 이는 비트마스킹으로 쉽게 표현할 수 있다. 13을 예시로 들어보면 13을 2진수로 표현하게 되면 1101이다. 즉 13인 방에서 갈수있는 방향을 왼쪽 오른쪽 아래 총 3가지 방향만 갈 수 있다. BFS를 돌 때 dir방향인 dy[4] dx[4]배열을 만들어 놓는데 이와 같은 방향일 때 내가 있는 공간에서 막혀..
https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 1. Logic 이 문제를 풀 때는 산봉우리의 의미를 잘 파악하는 것이 중요하다. 문제에서 정의한 산봉우리는 " 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.)" 라고 했다 인접은 X, Y좌표가 1이하로 차이나야 하기 때문에 (1,1)을 중심으로..
