컴퓨터 공학 기초/알고리즘 (BFS, DFS)
-
백준 2206 (벽 부수고 이동하기)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 23:32
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 해당 문제는 N by M 크기의 격자판이 주어지고 해당 격자판에서 N , M의 위치까지 최단거리를 찾는 문제이다. 이때 이동시 지켜야할 규칙이 존재한다. 규칙은 다음과 같다. 맵 밖으로 벗어날 수 없다. 맵에는 벽이 존재하며 벽 1개 까지는 뚫고 갈 수 있다. 이동 방향은 위, 아래, 좌, 우측으로 이동이 가능하다. 여기서 핵심은 벽을 최대 1개까지 뚫고 가면서 이동할..
-
백준 1261 (알고스팟)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 19:15
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해당 문제는 M * N 크기의 미로가 주어지며 (벽은 1 , 빈 공간 0) 해당 미로의 1 by 1 의 위치에서 N M 의 위치 까지 이동한다고 했을 때 가장 적은 수의 벽을 깨고 갈 수 있는 경우에 깬 벽의 횟수를 구하는 문제이다. 일반적인 Queue를 사용한 BFS탐색을 이용할 경우 결국 모든 경우를 모두 순회 해야 함으로 Queue 메모리 초과가 발생한다. 따라서 Deq..
-
백준 13549 (숨바꼭질 3)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 26. 18:27
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 해당 문제는 수빈이의 위치와 동생의 위치가 주어질 때 수빈이가 동생을 찾을 수 있는 가장 빠른 경우의 시간을 찾는 문제이다. 이때 수빈이의 이동할 수 있는 경우는 다음과 같다. 수빈이는 1초 뒤에 +1, -1 번의 위치로 이동할 수 있다 수빈이는 0초 뒤에 현재위치 * 2 의 위치로 이동할 수 있다. 위의 조건대로 움직인 좌표를 Queue 에넣고 BFS를 사..
-
백준 2178 (미로 탐색)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 17:24
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N by M크기의 미로가 주어지며 시작점이 1 by 1 의 위치일 때 N by M 의 위치에 도달하기 까지 걸리는 최소 이동 횟수를 구하는 문제이다. #include #include #include using namespace std; struct Node{ int y, x; int cnt; }; int n, m; int checkY[4] = { 0, 0, 1, -1 }; int checkX[4] = { 1, -1, 0, 0 }..
-
백준 4963 (섬의 개수)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 17:07
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net M by N 크기의 격자판이 주어지며 이 격자판 안에는 육지와 바다가 있다. 육지는 상하 좌우 대각선 방향으로 이어질 수 있으며 이렇게 이어진 육지를 하나의 섬으로 본다. 이때 섬의 개수를 구하는 문제이다. 풀이 : BFS를 이용한 탐색 #include #include #include #include #include #include using namespace std; struct Node{ int y,..
-
백준 2667 (단지번호붙이기)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 15:58
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 해당 문제는 0과 1로 이루어진 격자판이 주어지며 해당 격자판의 1은 집을 의미하고 0은 빈 집을 의미한다. 이때 집들의 모임인 단지를 정하고 단지의 개수와 각 단지마다 포함 된 집의 개수를 오름차순으로 출력하는 문제이다. 단지는 상하좌우로 인접한 집들의 집합이다. 풀이 : 2 중 for를 사용하여 격자판을 모두탐색 하며 만약 처음 방문하는 집일 경우에 BFS를 통한 상하좌우 방향의 집 탐색을 진..
-
백준 11724 (연결 요소의 개수)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 21. 03:30
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 해당 문제는 N개의 정점과 M개의 간선들이 주어질 때 하나로 연결 된 요소들의 총 개수를 구하는 문제이다. 풀이 : for 문을 사용하여 N개의 정점을 BFS를 사용하여 탐색하며 탐색한 정점은 check 해주며 Check 되지 않은 정점이 있을 경우 해당 정점에서 다시 BFS를 사용하여 정점을 탐색하는 과정을 반복하면서 check되..
-
백준 1260 (DFS와 BFS)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 21. 03:10
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해당 문제는 N개의 정점이 주어지면 해당 정점들의 간선의 정보가 주어지면 해당 정점들의 간선을 통해 연결 되어 있는 정점들을 DFS, BFS로 탐색을 하며 탐색되는 각 정점을 출력하는 문제이다. 이때 하나의 정점에 연결 된 간선이 여러개라면 숫자가 작은 정점을 방문하는 조건이 있다. 주의 사항 : 하나의 정점에 간선이 여러개일 경우 숫자가 작은 정점부터 방문해..