목록알고리즘/BFS, DFS (22)

키베이루's diary

[C++] 백준 2206번 벽 부수고 이동하기

1) 문제설명 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2) 아이디어 벽을 한 번만 부술 수 있기 때문에 처음에는 단순히 벽이 가로막고 있고 그 벽 다음이 뚫려있다면 벽을 뚫고 BFS를 순환하도록 구현하였는데 철저하게 틀린 답이었다. 먼저 벽을 뚫었을 때의 거리와 벽을 뚫지 않았을 때의 거리 중 뭐가 최소가 나오는지 알 수 없었고 벽을 먼저 뚫고 지나가면 나중에 나오는 벽을 뚫을 수없어 목표지점에 도달하지 못할 ..
알고리즘/BFS, DFS 2022. 6. 13. 12:07
[C++] 백준 16928번 뱀과 사다리 게임

1) 문제설명 2) 아이디어 주사위를 최소로 굴리는 횟수를 출력해야 하기 때문에 BFS를 사용했다. 반복문을 사용하여 주사위를 굴려서 도착한 곳이 사다리 or 뱀이 있는 곳이면 사다리 or 뱀의 목표지점으로 이동한다. 방문처리에 유의하며 BFS를 구현하면 문제없이 해결할 수 있다. ※ 서로 다른 위치의 사다리에서 같은 곳으로 이동할 수 있고 뱀을 타고 내려가도 최소 횟수로 이동할 수 있는 점을 유의한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr[120]; int range[120] = { 0, }; int n, m; int result; queue a; i..
알고리즘/BFS, DFS 2022. 6. 11. 12:50
[C++] 백준 7579번 토마토

1) 문제설명 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 2) 아이디어 기존 7576번의 토마토에서 층을 더 쌓아올린 문제이다. 풀이는 기존 7576번의 토마토와 같다. 7576번 토마토 참고 : https://kiveiru.tistory.com/32?category=557954 [C++] 백준 7576번 토마토 1) 문제설명 2) 아이디어 1. BFS의 시작점이 여러 곳이다 2. 전개가 막혀있는 부분이 있다. 3...
알고리즘/BFS, DFS 2022. 6. 11. 05:53
[C++] 백준 1697번 숨바꼭질

1) 문제설명 2) 아이디어 동생을 찾는 가장 빠른 시간을 찾기 위해서 BFS를 사용했다. 시작 지점에서 +1, -1, +현재 좌표로 식을 세워서 BFS 탐색을 실시하면 쉽게 구할 수 있다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr[100001]; int range[100001]; int cnt = 0; int dfs(int x, int k) { queue q; arr[x] = 1; q.push(x); if (x == k) { return 0; } while (!q.empty()) { x = q.front(); q.pop(); int dx[] = { -1,..
알고리즘/BFS, DFS 2022. 6. 10. 17:39
[C++] 백준 7576번 토마토

1) 문제설명 2) 아이디어 1. BFS의 시작점이 여러 곳이다 2. 전개가 막혀있는 부분이 있다. 3. 전개가 막혀서 0(익지 않은 토마토)을 1(익은 토마토)로 바꾸지 못할 경우 -1을 출력한다. 정도만 해결한다면 기본 BFS문제와 다른 점이 없다. 1번의 경우 시작점을 미리 큐에 넣어둠으로써 해결하였고 2번의 경우 if문으로 예외 처리하였다. 3번의 경우는 BFS를 사용해서 0 (익지않은 토마토)을 1 (익은 토마토)로 교체해 준다음에 배열 처음부터 끝까지 순회하면서 0이 있다면 -1을 출력하는 것으로 해결하였다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int a..
알고리즘/BFS, DFS 2022. 6. 10. 14:40
[C++] 백준 7562번 나이트의 이동

1) 문제설명 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2) 아이디어 나이트의 최소 이동 횟수를 구해야 하기 때문에 bfs를 사용한다. 나이트의 이동 규칙은 (1,2) (1,-2) (2,1) (2,-1) (-1,2) (-1,-2) (-2,1) (-2,-1) 이므로 그에 따른 배열을 만든다. 이에 따라 BFS탐색을 한다면 쉽게 나이트의 최소 이동 횟수를 구할 수 있다. ※ 여러 번의 테스트 케이스를 구해야 하기 때문에 memset을 사용하여..
알고리즘/BFS, DFS 2022. 6. 10. 08:20
[C++] 백준 2178번 미로 탐색

1) 문제설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2) 아이디어 거리의 최소를 찾기 위해 BFS를 사용했다. 처음 좌표를 (1,1)로 설정하고 BFS를 통해 값이 1인 곳을 찾아 탐색하였다. BFS로 탐색하기 때문에 1이 존재하는 모든 구간을 탐색한다. 따라서 전역 변수를 설정하여 1인 곳을 방문할 때마다 카운트를 세어주는 것이 아닌 거리에 따른 변수를 하나 설정하여 카운트를 센다. 또한 방문한 곳을 표시하거나 초기화시켜주지 않으면 큐의 메모리 초과가 일어나므로 ..
알고리즘/BFS, DFS 2022. 6. 9. 11:03
[C++] 백준 1012번 유기농 배추

1) 문제설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2) 아이디어 DFS를 사용하여 1이 연속으로 되어있는 구간일 경우 카운트를 세 주었다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; priority_queue v; // 우선순위 큐를 오름차순으로 정렬 int arr[55][55]; int cnt = 0; void..
알고리즘/BFS, DFS 2022. 6. 8. 12:57
Prev 1 2 3 Next