반응형 Algorithm/BFS16 [BFS, 합집합] 백준 11724번 연결 요소의 개수 (2가지 방법) BFS 기준으로는 난이도 하, 합집합 기준으로는 난이도 중하를 주고싶다. 1. BFS 알고리즘 꼬지 않은 평범한 BFS 문제이다. 평균 BFS 알고리즘 문제 정답율보다 높은 편인 46%의 정답율을 가지고 있는데 연결 요소가 몇 개인지, 다른 말로 몇 개의 연결그룹으로 되어있는지 계산하는 문제이다. FOR문으로 모든 정점을 탐색하여 방문하지 않은 노드에 대해서만 BFS를 수행하고, while문이 끝날 때 그룹 수를 1씩 더해주면 해결 된다. #include #include #include #include #include #include #include using namespace std; vector a[1001]; bool visited[1001]; int main() { ios_base::sync_wi.. 2020. 8. 9. [BFS, 난이도 중] 백준 1697번 숨바꼭질 정답율은 약 24%로, 쉬운 문제는 아니다. 하지만 이 문제가 왜 BFS 알고리즘을 요하는지 이해한다면 그렇게 복잡한 문제는 아니다. 개인적으로 이 문제의 정답율이 낮은 이유는 주어진 예제가 하나 뿐인 이유도 있겠지만, x좌표의 범위에 대한 처리가 헷갈려서 그렇다고 생각한다. 예를 들어 x좌표가 0일 경우에는 뒤로 갈 수 없고 x좌표가 50000을 초과하는 경우에는 순간 이동을 할 수 없다. 이에 대한 처리를 부가적으로 해줘야 한다. 이 문제는 1차원 BFS 문제이다. 수빈이의 초기 x좌표를 큐에 넣고 시작한다. 방문 여부는 time배열의 값이 0인지 아닌지를 따졌다. (0 -> 아직 방문 안함) 본인은 초기 시간을 1로 설정했기 때문에 time배열의 k(동생좌표)인덱스값 time[k] 에서 1을 뺀 값.. 2020. 8. 8. [BFS, 난이도 중하] 백준 7576번 토마토 https://kimcoder.tistory.com/16 [BFS, 난이도 하] 백준 2178번 미로 탐색 이제 BFS 응용문제다. 이 문제를 풀면 대충 BFS가 뭔지 감이 잡힐 것이다. BFS의 원리와 소스코드를 모른다면 이 글을 읽고 오는 것을 추천한다. https://kimcoder.tistory.com/15 [BFS, 난이도 하] 백준 1260번 D kimcoder.tistory.com 미로 탐색 문제처럼 time 배열을 쓸것이다. 다시 한번 설명 하지만, time배열은 각 좌표의 토마토가 언제 익게 되었는지의 시각을 의미 한다. 미로 탐색 문제와 다른 점은 시작점이 꼭 하나는 아니라는 것이다. 즉, BFS의 while문을 수행하기 전에 큐에 여러 좌표를 넣고 시작할 수도 있다는 것이다. 이 것 .. 2020. 8. 8. [BFS, 난이도 중하] 백준 1012번 유기농 배추 https://kimcoder.tistory.com/17 [BFS, 난이도 중하] 백준 2667번 단지번호붙이기 이 문제 같은 경우에는 1의 그룹이 몇개인가를 찾으면 된다. 이중 for문으로 방문되지 않은 '1' 요소를 찾아 그 좌표를 큐에 넣고 BFS를 수행해주면 된다. 맨 먼저 (0,1) 좌표를 중심으로 bfs가 수행되 kimcoder.tistory.com 단지번호붙이기 문제와 풀이법이 비슷하다. 약간 차이점이 있다면 테스트 케이스가 있으며, 가로와 세로의 길이가 따로 주어진다는 것이다. 가로, 세로 따로 주어진다는 사실을 못보고, 단지번호붙이기 소스코드를 그대로 복붙해서 테스트케이스 반복문만 추가해줬다가 이유도 모른채 틀렸습니다 라는 문구를 보게 되는 피해자는 발생하지 않기를 빈다. 마치 나처럼 그.. 2020. 8. 8. [BFS, 난이도 중하] 백준 2667번 단지번호붙이기 이 문제 같은 경우에는 1의 그룹이 몇개인가를 찾으면 된다. 이중 for문으로 방문되지 않은 '1' 요소를 찾아 그 좌표를 큐에 넣고 BFS를 수행해주면 된다. 맨 먼저 (0,1) 좌표를 중심으로 bfs가 수행되며 7개의 '1'이 첫 그룹으로 묶일 것이다. bfs과정중 (0,2) 좌표도 방문처리가 되었으므로 이중 for문에서 (0,2)는 넘어가게 될 것이고 (0,4)좌표를 중심으로 두번 째 그룹핑을 수행할 것이다. 그룹핑이 끝날 때마다 즉, while문을 탈출할 때마다 단지번호를 1씩 늘려가며 마지막에 최종 단지번호를 출력하면 문제가 해결된다. #include #include #include #include #include #include #include using namespace std; int ma.. 2020. 8. 7. [BFS, 난이도 하] 백준 2178번 미로 탐색 이제 BFS 응용문제다. 이 문제를 풀면 대충 BFS가 뭔지 감이 잡힐 것이다. BFS의 원리와 소스코드를 모른다면 이 글을 읽고 오는 것을 추천한다. https://kimcoder.tistory.com/15 [BFS, 난이도 하] 백준 1260번 DFS와 BFS BFS, DFS 알고리즘의 기본 원리를 공부한 사람이라면 쉽게 풀 수 있을 만한 문제이다. BFS(너비우선탐색)는 자신의 노드 주변에 자신이 갈 수 있는 경로들부터 탐색하는 알고리즘으로, 방문하지 않� kimcoder.tistory.com 이 문제에서 주의해야 할 것 하나는 입력을 따로따로 받는것이 아닌 행 단위로 받는다는 것이다. 그래서 110110을 입력받았을때 하나하나 쪼개서 배열안에 넣어주는 작업을 해야한다. 이 문제도 일반 BFS원리를.. 2020. 8. 7. [BFS, 난이도 하] 백준 1260번 DFS와 BFS BFS, DFS 알고리즘의 기본 원리를 공부한 사람이라면 쉽게 풀 수 있을 만한 문제이다. BFS(너비우선탐색)는 자신의 노드 주변에 자신이 갈 수 있는 경로들부터 탐색하는 알고리즘으로, 방문하지 않은 노드들을 모두 큐에 넣고 큐를 하나씩 빼내어 반복해내는 방법을 이용한다. DFS(깊이우선탐색)는 자신의 노드 주변에 자신이 갈 수 있는 경로들중 하나씩을 골라서 탐색 할 수 있는 노드가 없을 까지 깊이 들어가서 탐색하는 알고리즘으로, 큐 대신 스택을 이용 할 수 있으나 재귀함수를 쓰는게 편할 수 있다. 시스템상 재귀함수도 스택의 원리이기 때문이다. 사진과 소스코드와 함께 문제를 풀어보자. 이 사진은 예제코드 2를 그린 그림이다. 우선 간선 연결 정보를 배열a 벡터에 넣어야 하는데 출력 조건중 방문할 수 있.. 2020. 8. 7. 이전 1 2 다음
