전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 특이한 8방향 그래프 이동을 통해 원하는 목적지에 도달할 수 있는지를 구하는 문제입니다. 상이 왕을 잡을 수 있는 횟수가 얼마인지를 구하는 문제입니다. 상이 이동할 수 있는 8방향을 통해 계속 이동하면서 왕이 있는 곳까지 움직이면 되는 문제입니다. 주의할 점은 상이 이동하는 길에 다른 말이 있을 경우 해당 방향으로 움직일 수 없다는 것입니다. 해당 조건만 주의하면 쉽게 풀 수 있는 문제입..

문제 링크입니다. https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net BFS의 순서를 확인할 수 있는지를 물어보는 문제였습니다. 1번부터 BFS 탐색을 시작했을 때, 주어진 순서가 올바른 BFS 방문 순서인지를 확인하는 문제입니다. 부모가 같은 노드가 다수일 경우, 방문 순서가 여러개가 나올 수 있습니다. 문제 예시에서는 (1, 2, 3, 4) or (1, 3, 2, 4)가 나올 수 있습니다. 여러개가 나올 수 있는 방문 순서 중 하나가 입력에 주어졌는지를 찾아야합니다. 나올 수 있는 모든 경우를 확인하는 방법보다는 문제에서 나온 경우만을 맞는지 확인하는 것이 효..

문제 링크입니다. https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net BFS와 구현, 브루트포스가 합쳐진 문제였습니다. 문제 자체는 간단하지만 구현 능력이 있어야했던 문제입니다. 5개 층의 Map이 주어지고, 이를 통해 미로를 구성한 뒤 탈출할 수 있는지를 확인하는 문제입니다. 이 문제를 풀기 위해서 구현해야할 것이 있습니다. 1. 5개 층을 선택하기 2. 층을 반시계 혹은 시계 방향으로 돌리기 3. 구성된 미로를 탐색하기 먼..

문제 링크입니다. https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 이전과 이후를 비교하는 문제였습니다. 백신을 맞기 전과 후의 MAP을 주고 백신을 맞은 확률이 있는지를 알아보는 문제였습니다. 백신을 한번만 맞을 수 있다는 것이 중요했습니다. 이전과 이후의 MAP을 비교해서 다른 곳이 하나 있다면 해당 점에서 4방향 탐색을 시작합니다. 탐색을 완료한 뒤에 두개의 MAP을 비교해서 다른 경우 NO, 같은..

문제 링크입니다. https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 4방향 탐색으로 친구를 찾아주는 문제였습니다. 'I'에서 시작해서 4방향 탐색으로 'P'를 찾는 문제였습니다. 'X'를 제외한 모든 곳을 탐색할 수 있음으로 이를 유의하여 문제를 풀면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #i..

문제 링크입니다. https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 간단한 4방향 그래프 탐색 문제입니다. map이 주어졌을 때, 양 무리가 얼마나 있는지 구하는 문제입니다. 양이 있는 곳을 찾은 뒤, 해당 좌표에서 4방향 탐색을 이어가서 얼마나 양이 이어져 있는지 확인합니다. 탐색이 있을 때마다 양 무리를 하나씩 증가시켜주면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS ..

문제 링크입니다. https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 브루트포스와 BFS가 합쳐진 문제였습니다. map이 주어졌을때, 상어와 가장 멀리 떨어진 위치를 찾는 곳입니다. 주어질 수 있는 map의 크기가 크지 않기 때문에 모든 곳에서 상어와 떨어진 거리를 확인해보면 되는 문제입니다. for문을 통해, map의 값이 0인 모든 곳에서 8방향 탐색을 시작해 1과 만나면 바로 탈출해주면 됩니다. 이때의 이동거리를 ..

문제 링크입니다. https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 간단한 4방향 BFS 문제였습니다. 목표 지점이 2로 주어지고, 어느 점이든 목표 지점까지 갈 수 있는 최단 거리를 구하는 문제입니다. 최단 거리를 구하는 문제이기 때문에 DFS가 아닌 BFS로 풀어야 합니다. 목표 지점에서 역으로 출발해 어느 점이든 간의 최소 거리를 구하면 풀 수 있는 문제입니다. 자세한 것은 코드를 참고해주세요 #..

문제 링크입니다. https://www.acmicpc.net/problem/12761 12761번: 돌다리 동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대 www.acmicpc.net 문제만 길지 어렵지 않은 문제였습니다. 동규가 이동할 수 있는 경우는 8가지입니다. +1, -1, +A, -A, +B, -B, *A, *B 이렇게 이동할 수 있습니다. 따라서 현재좌표에서 해당 이동 방법을 모두 확인해보고 맞는 경우만 탐색을 이어나가면 됐습니다. 자신의 좌표가 0이상 100,000 이하여야 하니, 해당 조건을 만족하는지부터 확인해줘야합니다. 자세..

문제 링크입니다. https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net M개 만큼 BFS를 수행하면 되는 문제였습니다. 먼저 노드와 cost를 백터를 통해 이어줍니다. 그 다음 M개만큼 시작점, 끝점을 받아 BFS를 돌려주면 됩니다. 이때 check의 값은 0이 아닌 -1로 해줘야지 조건이 편해집니다. 0로 거리의 값으로 포함되기 때문에 방문여부를 확인하기 위해서 -1를 저장해줬습니다. 또한, 구조가 트리이기 때문에 어느 곳을 먼저 방문했더라도 최단거리가 나옵니다. -> 다익스트라가 아닌 BFS..

문제 링크입니다. https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 검을 얻었을 경우, 검을 얻지 못했을 경우로 나눠서 탐색을 진행해주는 것이 중요한 문제였습니다. 검을 얻었을 때는 벽을 제한없이 부실 수 있으며, 검을 얻지 못했을 경우는 정해진 길로밖에 가지 못합니다. 따라서 용사가 탐색을 하는 방법은 1. 검을 얻었을 경우 2. 검을 얻지 못했을 경우 이 2가지로 나눌 수 있습니다. 2가지 방법을 BFS에서 같이 돌려줘야 하는..

문제 링크입니다. https://www.acmicpc.net/problem/14716 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 8방향 탐색을 하는 간단한 BFS 문제였습니다. 0과 1로 이루어진 map에서 1로만 이루어진 영역을 찾는 문제였습니다. 다른 문제와는 다르게 대각선까지 포함한 8방향 탐색을 해야됨을 유의했다면 쉽게 풀 수 있던 문제입니다. 먼저 map을 전부 확인해본후, 1이 있는 곳을 확인합니다. 이때, 이전에 방문했던 곳은 아니여야 합니다. 조건을 만족했다면 해당 점부터 8방향 탐색을 시작해 글자가 어디까지 이어져있는지를 확인합니다. 자세한 것은 코드를 참고해주세요 #define _CRT_S..