Algorithm/BOJ(백준)
-
백준 14502 연구소Algorithm/BOJ(백준) 2018. 10. 3. 15:08
문제 링크 : https://www.acmicpc.net/problem/14502※선행해야 할 알고리즘 : BFS/DFS Algorithm 요약 : 벽을 3개를 임의의 위치에 놓고 상하좌우로 퍼지는 바이러스가 비어있는 곳에 퍼졌을 때 안전한 구간의 개수의 최대값를 출력하시오. 1. 2는 바이러스, 1은 벽, 0은 비어있는 곳 이라고 할 때, 비어있는 0에 벽을 임의로 3개를 세운다. 이 작업은 재귀함수로 진행하며 벽을 3개 세움과 동시에 BFS를 진행하여 반환해주고 다시 0으로 바꿔야한다.(그래야 recorvery 이후에 다음 벽을 세우기 때문에) 입력 예제 2를 예로 들면 다음과 같다 첫 번째 세워진 벽3개는1 1 1 0 0 01 0 0 0 0 21 1 1 0 0 20 0 0 0 0 2 두 번째 세워진..
-
백준 7562 나이트의 이동Algorithm/BOJ(백준) 2018. 10. 2. 22:35
문제 링크 : https://www.acmicpc.net/problem/7562※선행해야 할 알고리즘 : BFS/DFS Algorithm : I크기의 체스판에서 시작점부터 종료점까지 나이트의 이동거리를 출력하시오. 1. I*I크기의 체스판에서 시작점과 종료점을 준 후 나이트의 이동거리를 T개 구하는 문제이다. 가장 먼저 해야할 일은나이트의 8개 이동방향을 코드로 작성하는 것이다.BFS를 진행 할 시 모든 이동방향을 고려하여 queue에 삽입 후 종료점을 만났을 때 return하기 때문이다.따라서, 해당 코드를 작성하면 아래와 같다. int dy[] = { 1, 1, -1, -1, 2, 2, -2, -2 };int dx[] = { -2, 2, -2, 2, -1, 1, -1, 1 }; 2. 또한 입력 시 시..
-
백준 2468 안전 영역Algorithm/BOJ(백준) 2018. 10. 2. 22:25
문제 링크 : https://www.acmicpc.net/problem/2468※선행해야 할 알고리즘 : BFS/DFS Algorithm : 그래프를 입력받아 높이에 따라 안전한 영역의 군집 개수 중 가장 큰 값을 출력해라. 1. 먼저, 풀기 전 문제를 확실히 이해 할 필요가 있다. 입력 예제를 봤을 때, 6 8 2 6 23 2 3 4 66 7 3 3 27 2 5 3 68 9 5 2 7 이런 식으로 있는데 출력은 5인 것을 확인 할 수 있을 것이다. 그 이유는 높이가 1이하인 모든 영역에 물이 차올랐을 때,높이가 2이하인 모든 영역에 물이 차올랐을 때,...높이가 100이하인 모든 영역에 물이 차올랐을 때, 를 기준으로 계산 후 영역이 제일 많았던 높이가 4일 때의 군집의 개수인 5가 되는 것이다. 2...
-
백준 1012 유기농 배추Algorithm/BOJ(백준) 2018. 10. 1. 23:00
문제 링크 : https://www.acmicpc.net/problem/1012※선행해야 할 알고리즘 : BFS/DFS Algorithm : BFS/DFS 를 활용하여 군집을 찾아 군집의 개수를 출력해라 1. 입력받은 m, n, k를 통해 그래프를 만든다 2. 그래프에서 1이 입력된 인덱스를 찾아 반환한다. 3. 반환된 인덱스를 기준으로 아래, 왼쪽, 오른쪽을 BFS하며 count 한다. 이 때, 1을 찾아 방문을 했기에 count의 초기값은 1이다. 또한 방문한 곳들은 그래프를 0으로 설정하여 다시 들리지 못하게 한다. 4. 1~3을 그래프에 1이 더 이상 없을 때까지 반복하여 count된 군집 개수를 반환한다. 5. 1~4를 queue를 활용하여 T번 반복하여 BFS를 진행하면 다음과 같다. #inc..
-
백준 2667 단지번호붙히기Algorithm/BOJ(백준) 2018. 9. 30. 20:30
문제 링크 : https://www.acmicpc.net/problem/2667※선행해야 할 알고리즘 : BFS/DFS Algorithm : BFS/DFS 를 활용하여 군집을 찾아 군집의 개수와 군집의 원소 개수를 오름차순으로 출력해라 1. 지도를 입력 후, 지도에서 1이 입력된 인덱스를 찾아 반환한다. 2. 반환된 인덱스를 기준으로 아래, 왼쪽, 오른쪽을 BFS하며 count 한다. 이 때, 1을 찾아 방문을 했기에 count의 초기값은 1이다. 또한 방문한 곳들은 지도를 0으로 설정하여 다시 들리지 못하게 한다. 3. 해당 count를 vector에 삽입하고, 1~3을 지도에 1이 더 이상 없을 때까지 반복한다. 예를 들어, 입력 예제 본다면701101000110101111010100001110100..