알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net BFS와 DFS를 모두 사용하는 문제였습니다. 방문할 수 있는 지점이 다수일 경우, 작은 수부터 출력하는 것을 주의해야 했습니다. 문제 접근 방법 1. 백터를 이용해 정점에서 갈 수 있는 다른 정점들을 저장합니다. 2. 시작 지점부터 DFS를 탐색하면서, 방문 노드를 출력합니다. 3. 시작 지점부터 BFS를 탐색하면서, 방문 노드를 출력합니다...

문제 링크입니다 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS 문제였습니다 문제 접근 방법 1. 미로를 입력 받는다. 2. (1,1) 부터 (N,M) 까지 BFS를 통해서 최소 거리를 탐색한다. 문제 접근 방법 - 2번 void bfs(int a, int b){ q.push({a,b}); while(!q.empty()){ int x1 = q.front().x; int y1 = q.front().y; q.pop(); for(int i = 0; i < 4; i++){ i..

문제 링크입니다 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net BFS 문제입니다. 문제 접근 방법 1. 4방향 탐색과, 말로 이동할 수 탐색을 만든다. 2. BFS를 통해, 말로 이동할때와, 4방향으로 탐색할때를 모두 확인한다. 3. 도착점의 좌표를 확인해 최솟값을 찾는다. 문제 접근 방법 - 2번 while (!q.empty()) { int x1 = q.front().x; int y1 = q.front().y; int k1 ..

문제 링크입니다 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net BFS 문제였습니다. 문제 접근 방법 1. 배추들의 좌표를 입력받은뒤, 배열에 배추의 존재여부를 표시한다. 2. For문을 통해서 배추가 존재하면서, 전에 방문하지 않았던 곳을 찾아 BFS를 실행한다. 3. 필요한 지렁이의 갯수를 출력한다. 4. Test_case 만큼 반복한다. 문제 접근 방법 - 1번 for (int i = 0; i > x >..

문제 링크입니다 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 간단한 bfs,dfs 문제였습니다. 저는 bfs로 풀었습니다. 문제 접근 방법 1. 연결된 컴퓨터들을 입력받은뒤, 각각의 백터에 저장한다. 2. BFS를 1번 컴퓨터 시작한다. 문제 접근 방법 - 1번 for (int i = 0; i > x >> y; com[x].push_back(y); com[y].push_back(x); } 연결..

문제 링크입니다 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.www.acmicpc.netBFS와 DFS를 동시에 사용하는 문제였습니다. 위와 같은 조건으로 다리를 연결해 건널 수 있는 최소 연결 갯수를 구하는 문제입니다. 간단한 문제 접근 방법은 1. 섬의 구역에 번호 붙이고 좌표 저장하기 2. A섬에서 B섬까지 갈 수 있는 다리를 구하기 3. 다리를 연결해주면서 최소수를 구하기 였습니다. 문제 접근 1. 현재 지도의 상태 입력받기 2. 지도에서 각각..

문제 링크입니다 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net DFS에 익숙하지는 않아 https://yabmoons.tistory.com/117 님의 접근 방식을 참고했습니다. DFS, BFS를 모두 사용한 문제입니다 1번 기능을 구현하는 함수, 3번과 4번을 구현하는 함수와 2번 기능을 구현하는 함수로 나누어서 풀었습니다. 접근방법 1. DFS를 통해 7명의 학생을 뽑습니다. (1,2,3,4,5,6,7)이나 (7,6,5,4,3,2,1)은 똑같..

문제 링크입니다 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. BFS를 이용해 풀었습니다. N*N의 입력이 주어졌을 때, 위의 조건을 따라서 인구 이동이 시작합니다. 왼쪽 그림은 인구 이동 전, 오른쪽 그림은 인구 이동 후의 모습입니다. 모든 나라가 국경선을 공유하기에 전부 인구가 달라진 모습을 볼 수 있습니다. 접근 방법 1. 이중 for문을 통해서 check배열의 값이 0일때 해당 칸부터 B..

문제 링크입니다 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 삼성 SW 역량 테스트 문제입니다. BFS를 이용하여 풀었습니다. 1. 현재 택시의 좌표에서 가장 가까운 손님에게 찾아간 뒤, 목적지까지 간다. 2. 목적지에서 가장 가까운 손님을 찾아간 뒤, 손님의 목적지까지 간다. 2 - 1. 가장 가까운 손님이 많을 경우, 행이 작은순으로 행이 같은 손님이 있을 경우 열이 작은 순으로 정렬한다. 3. 1..

문제 링크입니다 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 삼성 SW 역량 테스트 문제입니다. 아기 상어는 위와 같은 규칙으로 움직입니다. 문제를 해결하기 위해서 구현해야 할 기능은 상, 하, 좌, 우로 움직이며 갈 수 있는 칸 찾기, 규칙에 따라서 갈 수 있는 칸 정렬, 아기 상어의 정보 변경하기를 구현해야 합니다. 1. 기본 설정 아기 상어가 갈 수 있는 칸 중에서 자신이 먹을 수 있는 물고기가 있을 수 있습니다. 그렇다면 그 ..

문제 링크 입니다 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 문제입니다. 이렇게 4개의 연산을 할 수 있는 할 수 있는 계산기가 있습니다. 이 계산기에는 0 이상 10000이하의 수를 저장할 수 있다고 할 때 수 A에서 수 B로 바꿀 수 있는 최소 횟수의 연산을 구하는 문제입니다. 각각 연산을 구현한 다음에 BFS를 통해서 A에서 B까지의 연산 과정을 저장하면 됩니다. 처음에 vector를 이용해 연산 과정을 저장했지만..

문제 링크입니다. https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A 4 -> 8 -> 81 -> 162 이와 같은 방법으로 최소 횟수는 5입니다. 1. 주어지는 수의 범위가 10^9이기 때문에 int 범위는 넘습니다. 따라서 long long 형으로 선언해줍니다. 2. 처음에 큐에 (A,0)를 저장해서 BFS를 시작합니다. 3. X*2, X*10+1 각각 B ..