알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 1과 같이 DFS를 통해서 선택, BFS를 통해서 탐색을 하는 문제였습니다. 문제 조건과 출력예시는 위 링크를 참고해주세요! 문제 접근 방법 1. 입력과 같이 바이러스의 위치와 빈칸의 갯수를 저장한다. 2. 빈 칸의 갯수가 1개 이상일 때, 바이러스를 M개 만큼 선택해준다. 3. 바이러스가 M개 선택되었다면, BFS 탐색을 통해서 바이러스를 확산시킨다. 4. 빈 칸이 없다면 T를, ..

문제 링크입니다 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net BFS를 이용한 문제였습니다! 3차원 배열을 만든뒤, 0~8초까지의 벽의 움직임을 담고, 9방향 탐색을 하면 되는 문제였습니다. 문제 접근 방법 1. 벽의 위치를 vector를 이용해 저장합니다. 2. 벽의 갯수가 0개라면 1출력, 아니면 탐색을 시작합니다. 3. 0~8초까지 저장한 벽의 위치를 이용해 N초가 지났을때의 벽의 위치를 저장합니다. 4. 9방향 탐색을 통해서..

문제 링크입니다 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net DFS를 통해서 벽을 선택한후, BFS를 통해서 탐색하는 문제였습니다. (문제는 너무 길어서 생략하겠습니다) 문제 접근 방법 1. 입력을 받음과 동시에 빈칸을 저장한다. 2. 빈칸 중에서 3개를 순차적으로 고른다. 3. 고른 빈칸에 벽을 세운뒤 BFS 탐색을 통해서 바이러스를 퍼트린다. 4. 안전 영역을 구한다. 5. 벽이 전부 선택될 때까지 반복한다. 문제 접근 방법 - 1번 for (int..

문제 링크입니다 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문자열을 사용한 BFS 문제였습니다 N을 입력받아서 K번 수를 바꾼뒤 최댓값을 출력하는 문제입니다. N을 자릿수를 바꿔야하기에 string으로 선언해서 문자열로 사용했습니다. 문제 접근 방법 1. 수의 위치를 바꿀 수 없을 경우를 찾아서 -1를 return 해준다. 2. 수를 K번만큼 바꾼 뒤, 최댓값을 찾아서 출력해준다. 문제 접근 방법 - 1번 if (N.size() == 1 || (N.size() == 2 && stoi(N) % 10 == 0))..

문제 링크입니다 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 접근 방법 1. map을 입력받는다. 2. (1,1) 부터 BFS를 시작한다. -> check[x][y][k]로 만들었습니다. 이때 k는 벽을 얼마나 부셨는가? 입니다. 3. (N,M)에 도달했다면, 이동 횟수를 return 합니다 4. (N,M)에 도달하지 못했다면, -1를 return합니다. 5. return 값에 따라서 출력을 다르게 ..

문제 링크입니다 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 6방향 탐색을 이용한 탐색 문제였습니다! 문제 접근 방법 1. 입력과 동시에 시작 위치를 저장한다. 2. 6방향 탐색을 통해서 갈 수 있는 곳을 찾는다 -> 이전에 방문하지 않았으면서, building[i][j] == '.'인 곳 3. 탐색 중, 출구에 도착한다면 -> 이동 횟수를, 도착하지 못한다면 -> -1를 return 한다 문제 접근 방법 - 2번 + 3번 int bfs() { ..

문제 링크입니다 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제와 동일한 문제였습니다 https://junseok.tistory.com/63 백준 5427 - 불(C++) 문제 링크입니다 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동 junseok.t..

문제 링크입니다 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 문제 접근 방법 1. 상근이의 위치와 불의 위치를 입력과 동시에 저장한다. 2. 저장한 불의 위치에서 상하좌우로 불을 붙인다. 3. 불을 피해 상윤이의 위치에세 상하좌우로 이동한다. 4. 2번과 3번이 끝난뒤의 각 정보들을 큐에 저장한다. 5. answer값에 따라서 출력한다. 6. 1~5번을 Test_case 만큼 반복한다. 문제 접근 방법 - 2번 + 3번 + 4번 int bfs() { i..

문제 링크입니다 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 에라토스테네스의 체 + BFS를 이용하는 문제였습니다! 문제 접근 방법 1. 에라토스테네스의 체를 이용해 1000~9999까지의 소수를 구한다 2. 소수 한 쌍을 입력받은 뒤, 소수 경로를 구하는 BFS에 저장한다. 3. answer의 값에 따라 출력한다. 문제 접근 방법 - 1번 void find_prime_number() { for (int i = 2; i = 1000 && check[..

문제 링크입니다 https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net https://junseok.tistory.com/60 백준 13460 - 구슬 탈출 2(C++, 복습) 문제 링크입니다 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음..

문제 링크입니다 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 삼성 SW 역량테스트 기출 문제입니다. 답을 알기 전에는 매우 어렵지만, 원리를 알면 쉽게 풀리는 문제였습니다. 빨간 구슬과 파란 구슬을 동시에 움직이는 것을 구현하는게 핵심입니다! 문제 접근 방법 1. 처음 빨강, 파랑 구슬의 위치를 저장한다. 2. 빨간 구슬의 위치에서 상,하,좌,우에서 갈 수 있는 곳을 찾는다. 3. 빨간 구슬..

문제 링크입니다 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 접근 방법 1. 현재 남아 있는 치즈의 갯수를 확인한다. 2. 치즈가 남아있을 경우, 공기를 BFS를 통해서 탐색한다. 3. 공기와 접촉되어 있는 치즈를 녹은 상태로 만들어준다. 4. 치즈를 녹여준뒤, 다시 반복한다. 문제 접근 방법 - 1번 bool get_cheese() { int cnt = 0; for (int i = 1; i 마지막으로 남은 치즈를 출력할때 사용 문제 접근 방법..