전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net BFS를 이용한 문제입니다. 친구 사이가 얼마나 떨어져있나에 따라 점수가 달라집니다. 모든 사람과 친구 사이이면 1점, 친구의 친구 사이가 있다면 2점, 친구의 친구의 친구 사이가 있다면 3점이 됩니다. 즉, BFS 탐색을 할 때, 탐색의 깊이만큼 사람의 점수가 된다는 의미입니다. 1번 사람부터 N번 사람까지 각각 탐색을 해줘야합니다. 그러면, 1~N번 사람까지 자신의 점수가 구..

문제 링크입니다. https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 y; connect[x].push_back(y); connect[y].push_back(x); } solve(); return 0; } 질문 및 조언은 댓글을 남겨주세요

문제 링크입니다. https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net BFS를 이용해 푸는 문제입니다. 일반적인 상하좌우 4방향 탐색이 아닌, 나이트 이동인 8방향으로 탐색하는 문제입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF ..

문제 링크입니다. https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net bfs를 이용한 간단한 문제입니다. 쩰리가 -1에 도착할 수 있는지 구하는 문제입니다. 쩰리는 아래와 오른쪽으로만 이동할 수 있습니다. 이동할 때 한칸만 이동하는 것이 아닌, map에 있는 값만큼 움직여야 합니다, 따라서 움직이고 난 뒤, map의 범위를 초과하는지 확인하는 것은 필수입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #..

문제 링크입니다. https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 간단한 구현 문제입니다. 쩰리가 아래와 오른쪽만 갈 수 있다고 했을 때, -1에 도달할 수 있는지를 구하는 문제입니다. 한칸씩만 움직이는 것이 아닌, 주어진 map의 값만큼 움직입니다. 따라서 오른쪽으로 혹은 아래쪽으로 map만큼 움직였을 때, map의 범위를 벗어나는지를 확인해주는 것은 필수입니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNI..

문제 링크입니다. https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net BFS를 이용한 문제입니다. 문서를 얼마나 훔칠 수 있는지 구하는 문제입니다. 자신이 가지고 있던 열쇠와 얻은 열쇠를 통해 닫힌 문을 열 수 있기에 복잡했던 문제입니다. 먼저 상근이는 map의 바깥에서 접근할 수 있습니다. 그렇기에 이전에 저장했던 map 값이 다음 탐색에도 영향을 줄 수 있기에 이를 막아줘야합니다. 1. map을 모두 초기화하기 2. map의 주변에 일정한 값으로 저장해주기..

문제 링크입니다. https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 다익스트라를 사용한 문제입니다. 문제를 풀기위해 새로운 접근이 필요했습니다. 상근이가 두 죄수를 탈옥하기 위해 열어야하는 최수 문 갯수를 구하는 문제입니다. 실수할 수 있는 부분이 있어, 많이 틀렸던 문제입니다. 문제에서 문을 열 수 있는 사람은 상근이와 두 죄수입니다. 그렇다면 생각할 수 있는 경우는 3가지입니다. 1. 상근이만 문을 열어 죄수들을 데려갈 경우 2. 죄수1이 죄수2를 데리고..

문제 링크입니다. https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 + BFS를 이용한 문제입니다. 어떠한 최단 경로가 있을 때, 해당 경로를 지우고 난 뒤의 다음 최단 경로를 찾는 문제입니다. 최단 경로를 찾는 것은 간단합니다. 다익스트라 알고리즘을 사용하면 찾을 수 있습니다. 그 다음인 최단 경로를 지우는 것이 문제인데, 이는 BFS를 사용하면 됩니다. BFS를 통해 최단 경로를 지우기 전에, 다익스트..

문제 링크입니다. https://www.acmicpc.net/problem/24447 24447번: 알고리즘 수업 - 너비 우선 탐색 4 정점 1번에서 정점 2번, 정점 4번을 순서대로 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 4, 3, 0이다. 너비 우선 탐색 www.acmicpc.net BFS 문제였습니다. BFS 탐색을 할 때, 탐색 깊이와 탐색 순서를 저장해주는게 중요했던 문제입니다. 탐색 순서는 다른 정점을 방문할 때마다 1씩 증가하지만, 탐색 깊이는 이전 정점에서 1를 더한 값입니다. 두개를 잘 구분해주는게 중요합니다. 두 값을 곱한 뒤 더할 때는 int의 범위를 넘어가니 long long int ..

문제 링크입니다. https://www.acmicpc.net/problem/24446 24446번: 알고리즘 수업 - 너비 우선 탐색 3 너비 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2, 4번 노드이다. 3번 노드는 2번 또는 4번 노드의 자식이다. 5번 노드는 1번 노드에서 방문 될 수 없다. www.acmicpc.net 간단한 BFS 문제였습니다. 양방향 그래프와 시작점이 주어질 때, 1~N번까지 깊이를 구하는 문제입니다. 저는 check 배열을 하나 만들었습니다. check 배열의 값을 전부 -1로 초기화한 뒤, X번이 탐색될 때마다 연결된 정점의 check 값에서 1 더한 값을 저장해줍니다. 탐색이 모두 끝난 뒤, check 배열의 값을..

문제 링크입니다. https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 구현력을 요구하는 BFS 문제였습니다. 두 사람이 좌우에서 막대기를 던지면서 미네랄를 부술때, 마지막의 미네랄 모양을 구하는 모습입니다. 문제에서 주어진 조건을 보면 1. 좌 -> 우 -> 좌 와 같이 돌아가면서 던진다. 2. 아래층이 1이며 윗층이 N이다. 3. 떨어지는 클러스터는 1개이다. 해당 조건을 기본적으로 알고 문제를 접근해보겠습니다. 문제를 크게 나누면 3개로 나눌 수 있습니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net BFS로 풀 수 있는 문제입니다. 1~N번 사람과 연결된 사람들이 주어지고, 루머를 퍼트립니다. 이때 X번 사람이 몇분만에 루머를 믿는지를 구하는 문제입니다. X번 사람이 루머를 믿는 조건은 자신과 연결된 사람 중, 과반수 이상이 믿으면 X번 사람도 믿게 됩니다. 그렇다면 배열 하나를 만들어, X번을 탐색하려고 할 때마다 해당 배열의 값을 ..