BFS5 [알고리즘] BFS(너비 우선 탐색) 1. BFS(너비 우선 탐색) 문제 모음집 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 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmi.. 2024. 4. 3. [알고리즘] 위상 정렬(Topological Sorting) 1. 개요 및 대표 문제 1. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘 2. 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 수행 3. 시간 복잡도 = O(V + E) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2. 위상 정렬의 대표 예시 위의 이미지처럼 작업의 순서가 정해져 있을 때 작업을 정렬해주는 알고리즘이 바로 '위상 정렬'이다. .. 2023. 10. 2. [백준 C++] 14940번: 쉬운 최단거리 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 2. 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 3. 소스 코드 #include #include using namespace std; int N, M; int map[1003][1003]; // 지도 정보 int dist[1003][1003]; // 목표지점까지 거리 지도 정보 pair goal_pos; // 목표지점 위치 // .. 2023. 6. 5. [백준 C++] 21736번: 헌내기는 친구가 필요해 1. 문제 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 3. 소스 코드 #include #include using namespace std; int N, M; int res = 0; char map[601][601]; // map 정보 int visited[601][601]; // 방문 여부 체크 pair I_pos; // 도연이 위치 // 방향 배열(.. 2023. 6. 5. [백준 C++] 2206번: 벽 부수고 이동하기 1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 3. 소스 코드 #include #include #include #include #include #include #define INF 987654321 using namespace std; int N, M; int map[1003][1003]; int visited1[1003][1003]; // 벽을 .. 2023. 2. 8. 이전 1 다음
