Algorithm/BFS\DFS
[백준 1194번] 달이 차오른다, 가자. (C++)
https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 달이 차오른다, 가자 문제는 벽 부수고 이동하기, 말이 되고픈 원숭이와 유사하며, BFS와 백트래킹을 이용하여 해결할 수 있습니다. 문제에서 열쇠는 'a', 'b', 'c', 'd', 'e', 'f만 등장합니다. 따라서 비트마스킹을 사용한다면, 현재 갖고 있는 열쇠의 현황을 6비트로 표현할 수 있습니다. BitMasking 예를 들어 111111은 6개의 키를 모두 ..
[백준 9328번] 열쇠 (C++)
https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 열쇠 문제는 BFS로 해결할 수 있습니다. 상근이는 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있습니다. 따라서, 평면도의 크기를 h + 1, w + 1로 선언하고, 가장자리를 '.'로 채워놓는다면, 상근이는 어느 위치에서 시작하던 상관 없습니다. 알고리즘의 기본 틀은 아래와 같습니다. 평면도를 순회하면서, 현재 가지고 있는 열쇠로 열 수 있는 문을 모두 개방한다. 평면도를 순회한다. 문이나..
[백준 16920번] 확장 게임 (C++)
https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 확장 게임 문제는 BFS를 이용하여 해결할 수 있습니다. 현재 순서인 플레이어의 성을 한 칸씩 이동시키는 작업을 Si번씩 반복하면 됩니다. ⚠️ 단, Si가 최대 109이므로 Si을 반복하며 성을 한 칸씩 이동시키는 과정에서 시간 초과가 발생할 수 있습니다. 따라서, Sn-1번째 성을 옮길 때, 옮겨진 성이 없다면, Sn번째부터는 성을 이동시키지 않는 방법으로 시간 초과를 방지할 수 있습니다. ..
[백준 11725번] 트리의 부모 찾기 (C++)
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 부모 찾기 문제는 BFS를 이용하여 해결할 수 있습니다. 루트 노드부터 시작하여 인접한 노드를 방문하면, 현재 노드가 부모 노드가 되고, 인접한 노드가 자식 노드가 됩니다. 아래는 전체 코드입니다. #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector linked(n + 1); // 인접 리스트 for(int i =0; i ..
[백준 16928번] 뱀과 사다리 게임 (C++)
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀과 사다리 게임은 1차원 배열, BFS를 이용하여 최단 거리를 계산하여 해결할 수 있습니다. 1번에서 시작하여 +6번까지를 방문합니다. 단, 사다리 또는 뱀이 있는 칸인 경우, 사다리 또는 뱀을 통해 이동한 칸도 방문해야 합니다. 아래는 전체 코드입니다. #include using namespace std; int board[101]; int vis..
[백준 11403번] 경로 찾기 (C++)
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 경로 찾기 문제는 각각의 정점에 대해 BFS를 수행하여 해결할 수 있습니다. 단, 주대각선도 0이 될 수 있음을 주의해야합니다. 아래는 전체 코드입니다. #include using namespace std; int linked[100][100]; int adj[100][100]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i+..
[백준 11724번] 연결 요소의 개수 (C++)
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 연결 요소의 개수 문제는 BFS 또는 DFS를 이용하여 부분 그래프의 개수를 계산하여 해결할 수 있습니다. 간선 정보를 입력 받아 인접 리스트를 만들고, 각 정점에 대해 BFS 또는 DFS를 수행하면 부분 그래프의 개수를 구할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; #define u..
[백준 2606번] 바이러스 (C++)
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 바이러스 문제는 네트워크 상에서 연결되어 있는 컴퓨터의 쌍을 입력 받아 인접 리스트에 저장하고, 인접 리스트를 이용하여 BFS를 수행하여 해결할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; bool vis[101]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vect..