백준
-
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차원 배열을 사용했다. 때문에 오히려 쉬웠다. 아! 그..
-
7576 토마토알고리즘/백준 문제 2020. 5. 16. 00:16
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 기본 BFS 문제와 달라진 점은 출발점이 0,0이 아니면서 동시에 탐색을 해야하는 점 이전에는 출발점을 이중 for문으로 찾아서 한번 실행시켜주면 되었다. 이번에는 출발점이 여러개 일 수 있기 때문에 이중 for문으로 찾은 출발점들을 바로 넘겨주지 않고, 큐에 저장했다. 그 뒤로는 똑같음 딱히 어려운 점은 없었다.
-
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일..