BFS
-
1012 유기농 배추알고리즘/백준 문제 2020. 5. 16. 14:31
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 단지번호붙이기 문제의 난이도하향 버전이라고 볼 수 있겠다. 똑같은 방법으로 푸는데, 단지번호붙이기는 단지별로 아파트 개수를 세어야 했지만, 이 문제는 그럴 필요 없이 벌레의 개수(==단지의 개수)만 구하면 된다. 이중 for문을 돌면서 배추가 심어져있고 방문한 적 없는 위치인지 확인한다. 조건을 만족하면 카운트(필요한 벌레의 수)를 1 증가 BFS 탐색 카운트 값을 출력 그리고 이 전체 과정을 테스트케이스..
-
1679 숨바꼭질알고리즘/백준 문제 2020. 5. 16. 13:43
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 이 문제 역시 최소시간(최단거리)를 구하는 문제이기 때문에 BFS를 이용해서 풀었다. 큐에 들어갈 다음 경로는 문제에 나와 있듯이 3가지가 있다. x+1 x-1 x*2 이전 BFS문제들과 같은 방식인데, 다른 문제에서 동서남북으로 움직이던 것을 이 문제에서는 위의 3 가지 경우로 움직이면 되고 일직선 상의 경로니까 1차원 배열을 사용했다. 때문에 오히려 쉬웠다. 아! 그..
-
2178 미로탐색알고리즘/백준 문제 2020. 5. 14. 20:11
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - 미로의 시작 [0,0] 에서 [n-1, m-1]로 빠져나가는 최단거리를 구하는 문제 - 정점간의 거리가 모두 1 이므로 BFS를 사용하여 최단거리를 구할 수 있다. 탐색중인 위치(x,y) 를 표시할 클래스 Pos를 만들었다. 반복문을 이용해 이동가능한 상하좌우 좌표를 확인하기 위해 상하좌우로 이동시켜줄 _x, _y 배열을 생성했다. 즉 각각의 배열 인덱스 0은 '상' 으로 이동하기 위한 x좌표, y좌표를 담고 있다. 위와 같..
-
1260 DFS와 BFS알고리즘/백준 문제 2020. 5. 14. 18:40
입력값 : 4 5 1 1 2 1 3 1 4 2 4 3 4 - DFS (Depth First Search 깊이우선탐색) 한 방향으로 갈 수 있는 끝까지 탐색을 마치고, 그 다음 방향으로 탐색한다. 길이 여러개일 경우 숫자가 작은 정점부터 탐색하므로 1 -> 2 로 이동. 한 방향으로 탐색을 이어가야 하므로 1 -> 2 -> 4 -> 3 으로 이어진다. 마지막 3 에 도착했을 때, 1 과 4는 이미 방문 한 상태이므로 재귀로 호출된 스레드가 하나하나 모두 종료된다. 모든 정점을 방문 했으므로 프로그램은 종료된다. - BFS (Breath First Search 너비우선탐색) 한 정점에 도착했을 때, 그 정점에서 방문 가능한 정점은 모두 방문한다. 동시에 여러 정점을 방문하는 형태이다. 각 정점의 거리가 1일..