Angievelopment

✨ 문제 풀이 노드 i에서 노드 j까지 갈 수 있는 경로가 존재하는지 알아내는 문제이다. 즉 그 사이에 j, l, m ... 등 여러 개의 노드를 통해서 연결되어도 된다는 것이다. BFS를 통해서 연결되어 있는 노드들을 큐에 저장해서 탐색하면서 연결되어 있는지 저장해간다. 약간 다익스트라 알고리즘의 느낌도 난다. 여기서 중요한 것은 양방향 간선이 아니라 단방향 간선이라는 점! 따라서 사이클을 만들면서 자신으로 돌아오면 1이지만 사이클이 없으면 0이라는 것이다!! 나는 route라는 일차원 배열을 만들어서 한 노드가 다른 노드들과 연결 되어있는지 저장했다. route 배열을 0으로 초기화해주고, 방문하면 1을 저장한다. 이미 방문한 노드는 연결이 되어있다는 뜻이니 굳이 안 봐도 되고, 큐를 통해 방문하게 ..

다 풀고 나니까 쉬운 문제였는데.. 말도 안 되게 계속 헤매가지고 오래 걸렸다 😕 ✨ 문제 풀이 내가 생각했을 때 이 문제를 풀기 위해서 가장 중요한 부분은 다음과 같았다. 1. 맨해튼 거리 2 이하 내에 두 사람이 위치해 있으면 X 2. 두 사람 사이에 파티션이 존재하면 괜찮음 먼저 맨해튼 거리 2 이하라는 조건을 생각해보았다. 일직선 상에 2칸 이내와 대각선으로 한 칸 이내는 모두 맨해튼 거리 2 이하이다. 그리고 두 번째 조건에 대해 생각해보았다. 일직선 상에 있을 때는 두 사람 사이에 파티션이 존재하는 걸 쉽게 생각할 수 있지만, 대각선 상에 있을 때는 어떻게 파티션이 존재해야 하는지 생각해야 한다. 한 칸 대각선 위에 있는 사람과 거리두기를 만족하려면 두 사람을 이을 수 있는 동서남북 방향이 모..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ✨ 문제 풀이 BFS또는 DFS를 이용해서 해결할 수 있는 문제입니다. 1 6 6 3 3 5 4 1 2 4 4 7 연결된 노드의 정보가 위와 같다고 예시를 들어봅시다. 문제에 따르면 1은 무조건 루트 노드입니다. 따라서 1과 연결된 노드들은 모두 부모가 1인 노드입니다. 1과 연결된 노드는 4, 6입니다. 이 노드들에 대해서 차례대로 확인합니다. 4와 연결된 노드는 1, 2, 7 입니다. 1은 무조건 부모 노드이므로 2, 7이 자식 노드입니다. 즉 2, 7의 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ✨ 문제 풀이 간단한 BFS 해결 문제입니다. u와 v의 컴퓨터가 연결되어 있다면 u번째 배열에 v를 저장해주고, 마찬가지로 v번째 배열에 u를 저장해줍니다. 그리고 1번 컴퓨터와 연결되어 있는 모든 컴퓨터를 찾아야 하므로 BFS를 통해 연결된 컴퓨터를 하나씩 방문하면서 개수를 세어나갑니다. 이때 주의할 점은 1번에 영향을 받은 컴퓨터의 개수를 찾는 것이므로 1번 컴퓨터를 제외한 개수를 출력해야 합니다..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net ✨ 문제풀이 n*m 격자 모양 행렬을 BFS로 해결하는 문제입니다. 그러나 반복해서 전체 격자를 검색하면서 치즈가 전부 녹아서 없어질 때까지 진행해야 합니다. 이 문제의 가장 핵심은 '외부 공기'와 '내부 공기'를 구분하는 일입니다. '외부 공기'와 접촉이 없고 치즈에 둘러싸인 내부 공기에 닿은 치즈 면은 녹지 않는 면입니다. 바로 이 공기를 구분할 때 BFS를 사용합니다. '내부 공..

https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net ✨ 문제 풀이 2가 딱따구리 가족이므로 2의 (y, x)좌표가 시작점이 될 것입니다. 그리고 3, 4, 5는 딱따구리 가족이 각자 먹고 싶은 음식이고 종착점이 됩니다. 딱따구리 가족은 3, 4, 5 중 아무거나 하나만 가장 먼저 먹을 수 있는지만 구하면 됩니다. 1은 장애물이라 갈 수 없으며 0은..

n행, m열의 행렬을 받고 상하좌우 4방향으로 한 칸씩 옮기면서 해답을 찾아가는 BFS 문제를 해결하기 위한 응용 코드입니다. 문제에서 주어진 조건을 잘 읽고 아래 코드를 응용해서 풀이하면 됩니다. 🗓 코드 #include #include #include using namespace std; #define MAXINT 100 int dx[] = {0, -1, 0, 1}; int dy[] = {1, 0, -1, 0}; int n, m, start_y, start_x; int arr[MAXINT][MAXINT]; bool visited[MAXINT][MAXINT]; queue q; void bfs() { q.push({start_y, start_x}); while (!q.empty()) { int y = q..