Coding_Test_C++
BaekJoon 11559번: Puyo Puyo(C++)
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이법 1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) BFS알고리즘을 기준으로, 현재 색과 같은 색인 것들을 vector에 index를 담아주었다가, 갯수가 4개 이상인 경우 이 값들을 빈 공간으로 바꾸어 주었다. 3) 한번이라도 4번 이상 뿌요가 터진 경우에는 totalCount라는 결과값을 증가 시켰고, 빈 공간을 채워주..
BaekJoon 14442번: 벽 부수고 이동하기 2(C++)
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) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) k번 벽을 허물 수 있으므로, visited배열을 3차원 배열로 선언하였다. 허물지 않고 진행한 경우 wall이라는 변수를 현재 상태 그대로, 허문 경우는 wall+1로 두어서, 최대로 허물 수 있는 한도를 넘지 않도록 코드를 작성하였다. (3차원 배열로 작성하..
BaekJoon 14923번: 미로 탈출(C++)
https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 풀이법 1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) 마법을 사용하여 한 번 벽을 허물 수 있으므로, visited배열을 3차원 배열로 선언하였다. 허물지 않고 진행한 경우 magic이라는 변수를 0으로 한 번 허문 경우는 1로 두어서, 한 번 허물었던 경우 다시 허물고 지나가지 않도록 코드를 작성하였다. (3차원 배열로 작성하지 ..
BaekJoon 11060번: 점프 점프(C++)
https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 풀이법 1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) i번째 index에 있는 값 이하로 점프할 수 있기에 for문을 1부터 arr[index]까지 값으로 돌려 모든 경우의 수를 bfs 기반의 알고리즘으로 탐색하여 문제를 해결하였다. #include #include #include #include #define INF 987654321 u..
BaekJoon 11403번: 경로 찾기(C++)
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이법 1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다. 2) 각 행 별로 방문한 곳을 체크하는 visited배열을 초기화 해준 후 현재 갈 수 있는 값이 1인 경우를 확인하여, BFS기반의 알고리즘으로 탐색을 하여, 방문 가능한 node들을 visited배열에 담아 주었다. 3) 이후 makeArr2 함수를 통해 visited배열이 true인 곳들을 최종 답이 될 Arr2에 넣어줌으로써 문제를 해결..
BaekJoon 13901번: 로봇(C++)
https://www.acmicpc.net/problem/13901 13901번: 로봇 첫 번째 줄에는 방의 크기 R, C(3 ≤ R, C ≤ 1,000)가 입력된다. 두 번째 줄에는 장애물의 개수 k(0 ≤ k ≤ 1,000)가 입력된다. 다음 k개의 줄에는 각 장애물 위치 br(0 ≤ br ≤ R – 1), bc(0 ≤ bc ≤ C - 1)가 www.acmicpc.net 풀이법 1) 난이도가 어렵지 않은 시뮬레이션 문제였으나, 조건문을 짜는 과정에서 실수가 잦아서 여러 번에 끝에 정답에 도달할 수 있었다. (4%에서 계속 "틀렸습니다"가 나오시는 분들은 맨 밑의 TC를 확인하세요!) 2) bfs와 같은 재귀 과정을 사용하는 것이 더 효율적일 수 있으나 필자는 bfs 기반의 queue가 손에 익었기에 ..
BaekJoon 9372번: 상근이의 여행(C++)
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 풀이법 1) 그래프 이론을 활용하여, BFS나 DFS로 푸는 문제라 생각하여 시도 하였으나, 어이 없게도 답은 무조건 n-1이 나오는 문제이다. 2) 그래프 내의 모든 정점을 포함하는 트리이며, 최소 연결 부분 그래프이기에, MST로 문제를 푸는 것이 맞는데, n개의 정점을 갖는 MST의 최소 간선의 수는 n-1개 이기에 답은 항상 n-1이 된다. 3) 해당 ..
BaekJoon 3184번: 양(C++)
https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이법 1) BFS나 DFS 알고리즘을 활용하여, 빈 공간이 있거나, 양이 있거나, 늑대가 있는 칸들과 연결된 칸들을 반복하며 탐색하면 되는 문제이다. 2) 한 공간 내에 양이 더 많은 경우 늑대를 쫓아내고, 늑대의 수가 양과 같거나 많으면 양이 없어지는 것을 감안하여, 한 공간 내에서 양의 수와 늑대의 수를 구한 후 조건을 활용하여 코딩을 진행하였다. #include #include..
BaekJoon 4963번: 섬의 개수(C++)
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이법 1) BFS나 DFS 알고리즘을 활용하여, 연결되어 있는 섬의 개수를 세면 되는 간단한 문제이다. 2) 여러 개의 TC가 존재하므로 visited배열을 매번 초기화 시켜 주어야 한다는과 대각선 방향 또한 인접한 배열이라고 생각해야 한다는 점을 꼭 기억한다면 어렵지 않게 풀 수 있는 문제라고 생각한다. #include #include #include #include #include #i..
BaekJoon 3085번: 사탕 게임(C++)
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이법 1) 구현과 브루트 포스로 풀어내는 문제였다. 난이도가 높은 문제는 아니었으나, 반례를 고려해야 하므로 꽤 많은 시간을 투자하였다. 2) check 함수는 상하좌우로 연결되어 있는 배열의 값과 현재 배열의 값을 바꾸는 함수이다. 모든 경우의 수를 고려해야 하기에 이 부분에서 시간을 줄이겠다고 vistied배열을 썻으나 실패하여서 제거하니 통과가 되었다. 모든 값은 처음 입력 값의 배열인 arr를 copy한 arr2배열을 활용하여 확인하였다. 3) countMax() 함수는 각 행과 각 열의 연속된 최대 값을..