문제문제 설명기본적으로 맵의 구성은 다음과 같이 설명할 수 있다.'.' :이동 가능한 빈 공간'*': 이동 불가능한 벽'$': 훔쳐야 하는 문서알파벳 대문자: 문알파벳 소문자: 열쇠(알파벳 대문자와 동일 문자일 경우 가능(a열쇠는 A문에서 가능))맵이 주어진 다음에는 일련의 문자열이 주어지는데 이는 이미 가지고 있는 열쇠를 의미한다.만약 0이 주어진다면 초기에 가지고 있는 열쇠는 없다.cz: c와 z열쇠를 가지고 있음0: 열쇠 없음맵이 주어졌을 때 총 몇 개의 문서를 훔칠 수 있을지 알아내야 한다.문제 해설bfs일단 정점을 돌아보면서 다음과 같은 경우의 수를 모두 확인해 준다.1. '.'인 경우: 그냥 이동2. '$'인 경우: 문서의 개수를 +1해 주고 그 위치를 '.'으로 변경해 준다.3. 대문자 알파..

문제문제 설명모든 동굴은 통로로 연결되어 있다.이때 로봇은 인접한 동굴에 위치하게 된다면 통신이 가능하게 된다.동굴사이를 이동하기 위해서는 특정 길이의 통로를 통과해야 한다.최소한의 길이로 이동하도록 코드를 작성하시오.문제 해설bfs기본적으로 A동굴에서 B동굴로 이동하는 경로는 한 가지밖에 존재하지 않는다. 또한 A-B로 이동하는 경로 어디에서든지 만나도 상관이 없다. ex) 1-3-5-7의 경로가 있다고 할 때 동굴 1,3에서 만나도 상관없고, 3,5에서 만나도 상관없음. 즉 경로를 이동하면서 통로의 길이를 모두 더해준 다음, 제일 긴 경로를 빼주면 된다.최종 코드#include using namespace std; struct P {int a, sum, mx;}; int n, a, b; int vis..

문제문제 설명섬의 정의는 상하좌우 대각선 8방향과 인접한 땅이 있다면 그 부분을 하나의 섬으로 본다.이렇게 섬을 나누었을 때 개수를 구하시오.문제 풀이bfs를 활용하여서 방문 처리가 안 된 부분을 확인해 주면서 섬 하나에 포함되는 땅들을 방문 처리해 준다.섬 하나를 방문 처리 해준 다음에 +1씩 카운트해준다.최종 코드#includeusing namespace std;const int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,1,0,-1,1,-1,1,-1};int n,m;int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); while(true){ cin>>m>>n; if(n=..

문제문제 설명배열에서 1의 경우에는 이동할 수 없는 벽이 있는 곳이고 0이 있는 경우는 이동할 수 있는 곳을 의미한다.한 칸의 벽을 부수고 이동할 수 있는 부분을 구해준다.문제 해설처음에는 벽을 하나씩 부수면서 이동할 수 있는 공간을 모두 탐색하는 방식으로 문제를 해결하려고 하였지만 이럴 경우에는 시간초과가 발생할 가능성이 높기 때문에 다른 방법으로 접근해야 했다.모든 칸을 확인하면서 방문하지 않고 이동할 수 있는 부분부터 탐색을 시작한다. 그 칸부터 이동할 수 있는 부분이 몇 군데 있는지를 확인 해준다.이때 칸을 방문할 때 연결된 칸들은 같은 숫자로 체크해 주고 연결되지 않은 부분은 다른 숫자로 체크해 준다.그 칸을 방문하면서 체크했던 숫자를 인덱스로 하여서 이동할 수 있는 칸의 개수를 저장해 준다.그..

문제문제 설명BFS를 활용한 탐색 순서를 파악하는 문제이다.n개의 정점에 대해서 n-1개의 간선을 가지고 있다.아래의 그림에서는 1-3-2-4로 탐색을 하거나 1-2-3-4로 탐색할 수 있기 때문에 기존 BFS방식만 사용하면 안 된다.문제 접근BFS: 기존과 같게 BFS를 탐색하는 코드를 만들어줌.정렬: 각 정점에서 연결되는 다른 정점을 v [ (현제 정점) ].push_back( (다음 정점) )을 해줄 때에 (다음 정점)들은 정렬되지 않고 들어온 순서대로 저장되기 때문에 1-2-3-4와 1-3-2-4와 같은 순서를 파악할 수 없기 때문에 v[ (현제 정점) ]을 정렬해 줄 필요가 있다.최종 코드#include #include #include #includeusing namespace std;vecto..

문제문제 설명이 문제는 두 개 이상의 섬이 존재한다고 가정하고 한 섬에서 다른 섬으로 연결할 수 있는 가장 짧은 다리의 길이를 출력하는 간단한 문제이다. 그렇기에 단순히 너비 우선 탐색을 사용한다면 쉽게 해결할 수 있다.문제 해설#include#includeusing namespace std;int n;const int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };int a[201][201];int visited[201][201];int mn = 1e9;struct P { int b, c, d;};int f(int x, int y, int t) { int visited1[201][201]; fill(&visited1[0][0], &visited1[0][0] + 201 *..