전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net BFS or DFS를 이용해 푸는 문제입니다. BFS를 통해 W 혹은 B가 뭉쳐있는 수를 구한 뒤, 전체의 합에 더해주면 되는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include..

문제 링크입니다. https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS 이용해 푸는 문제입니다. 1번 바이러스부터 K번 바이러스까지 순차적으로 4방향으로 퍼트리는 문제입니다. 순차적으로 퍼지기에, 큐에 1번부터 K번까지 차례대로 넣어준뒤 BFS 탐색을 해야합니다. 코드에서 정렬을 한 이유는 1번부터 K번까지 순서대로 큐에 넣고 시작하기 위해 정렬을 해줬습니다. 탐색을 하는 중에서 큐에 새로운 데이터를 넣는 조건입..

문제 링크입니다. https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net BFS를 이용한 간단한 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; char Map[251][251]; bool check[251][251]; i..

문제 링크입니다. https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net BFS와 MST를 이용해 푸는 문제입니다. 저는 이 문제를 한 구역에서 다른 구역까지의 거리 최솟값을 저장한 뒤, Union-Find를 이용해 구했습니다. 로봇은 언제 생성하든 시간이 들지 않기에, MST를 통해 최솟값을 구하면 자연스럽게 풀리는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #..

문제 링크입니다. https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net BFS문제입니다. 1번점에서 시작했을때, N번점까지 갈 수 있는지를 확인하는 문제입니다. 저는 배열을 이용해 X번점에 도달할 수 있는 최소 점프 수를 저장했습니다. 먼저 해당 배열에 INF 값을 저장했습니다. 탐색이 끝났는데도 N번칸의 배열 값이 INF라면 -1을 출력하면 되며, INF 값이 아니라면 해당 칸의 값을 출력해주면 됩니다. X번칸에서의 탐색 범위는 해당 칸..

문제 링크입니다. 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 BFS 혹은 다익스트라 알고리즘을 사용해 푸는 문제입니다. X -> Y로 갈 수 있는 가중치가 1인 간선이 주어졌습니다. 이때 시작점에서 갈 수 있는 최단 거리가 K인 정점을 찾으면 되는 문제입니다. 가중치가 1이기 때문에 BFS를 통한 탐색 or 다익스트라 알고리즘 중 편한 것을 선택해 풀면 되는 문제입니..

문제 링크입니다. https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net BFS를 이용한 문제였습니다. 방문한 곳을 체크할 때, 위치를 다르게 해야지 풀리는 문제입니다. N부터 K까지 최소 거리 및 최소로 올수 있는 경우의 수를 모두 구하는 문제입니다. 다른 문제와 같이 방문함과 동시에 check 배열의 값을 바꾸어주면 정확한 값이 나오지 않습니다. 이런 경우에는 queue에서 현재 좌표를 pop을 한 뒤, che..

문제 링크입니다. https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 주사위 굴리기 + BFS가 합쳐진 문제였습니다. 주사위를 동서남북으로 바꿀때, 값이 어떻게 변하는지를 나타냈습니다. 이를 통해서 주사위를 구리는 것을 구현할 수 있습니다. 1. 주사위 방향 바꾸기 int change_way_180(int x) { if (x == 0 || x == 2) return x + 1; else ret..

문제 링크입니다. https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net BFS와 구현이 합쳐진 문제였습니다. 같은 색깔의 뿌요가 4개 이상인지를 찾은 뒤, 해당 뿌요들을 없앱니다. 그 뒤, 남아있는 뿌요를 아래로 내린 뒤, 다시 뿌요 그룹을 찾는 문제였습니다. 1. 같은 색의 뿌요 찾기 void puyo_boom(int a, int b, char c) { queue q; q.push({ a,b }); check[a][b] =..

문제 링크입니다. https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 삼성 SW 역량테스트 기출 문제였습니다. 그래프 탐색 + 구현 문제로 구현해야할 것이 많은 문제였습니다. 한 일반 블록에서 상하좌우로 접한 블록 그룹을 찾은 뒤, 조건에 따라 정렬을 합니다. 이때 블록 그룹에는 무지개 블록은 항상 포함 가능합니다. 크기 -> 무지개 블록 수 -> 기준 블록의 행 -> 기준 블록의 열 순으로 블록 그룹을 정렬하고 가장 큰 그룹을 제거합니다. 블..

문제 링크입니다. https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS를 이용한 문제였습니다. 기존 벽 부수기 문제와는 다르게 밤과 낮 기능이 추가된 문제였습니다. 따라서 저는 구조체를 이용해 queue에 현재 좌표, 벽을 부순 횟수, 이동 횟수, 밤과 낮을 저장해줬습니다. 해당 좌표를 방문했는지를 확인하는 check배열은 2차원 배열로 선언하면 안됩니다. 벽을 1번 부수고 (X,Y)에 도달할 수도 있으며,..

문제 링크입니다. https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 간단한 그래프 문제였습니다. X -> Y 까지 가는데 거쳐가야하는 수를 구하는 문제였습니다. 예시를 통해 확인해보겠습니다. 7 -> 3 을 가는데 7 -> 2 -> 1 -> 3 으로 이동할 수 있습니다. 따라서 촌수가 3이 됩니다. M개의 line이 주어졌을때, X와 Y를 서로 양방향으로 저장해줍니다. 시작점을 queue에 넣어준 뒤, 갈 수 있는 점들을 확인..