BFS (12) 썸네일형 리스트형 [알고리즘 깨알 팁] BFS 짜는 법 알고리즘을 풀면 아주아주 많이 마주치는 것이 바로 이 BFS입니다.BFS는 최단거리를 찾을때 굉장히 자주쓰이죠! BFS는 보통 큐를 이용한 방식을 사용합니다!큐의 가장 앞에 있는 노드를 불러서 다음노드들을 맨 뒤에 놓으면,결국 먼저왔던 노드들은 먼저 처리되고 나중에 불러진 노드들은 나중에 처리됩니다.BFS는 이런 특징을 이용해서, 같은 거리에 있는 어떤 지점을 처리한 뒤에 다음 거리에 있는 지점을 탐색할 수 있기 때문에 최단거리로 쓸 수 있는 것이죠! BFS에서 가장 중요한 것은 무엇일까요!?바로, 방문 체크를 잘 만들어야 한다는 것입니다!방문 체크를 잘 못만들면 큐에 들어갔던 값이 또 들어가고.. 또 들어가고... 또 들어가서 메모리가 터져버리거든요! 이렇게.. 무한 루프에서 빠져나올수 없게되죠.하지만.. [삼성 기출 문제] 백준 16236 아기 상어 문제 링크 어떻게 풀까? 시뮬레이션과 BFS가 함께 공존하는 혼돈의 문제입니다. 문제의 조건에 맞게 세세하게! 아주 세세하게! 잘 만들어야 합니다.개인적으로, 시뮬레이션이면 구조체를 활용하는 방법을 추천드립니다. 문제에 굉장히 햇갈리는 조건들이 많이 있습니다. 1. 아기 상어는 입력에서 9로 주어진다. (어려운 조건은 아니지만, 이것 때문에 고생을 많이 해서 올립니다.)2. 아기 상어는 처음에 크기가 2이다.3. 아기 상어는 자기보다 작은 물고기만 먹을 수 있다.4. 아기 상어는 자기보다 크기가 큰 물고기가 있는 칸은 지나갈 수 없다.5. 아기 상어는 다음과 같은 조건에 맞춰서 이동한다.- 아기 상어가 먹을 수 있는 물고기가 없으면 엄마에게 도움을 요청한다! (귀엽..)- 먹을 수 있는 물고기가 1마리라.. [삼성 기출 문제] 백준 16234 인구 이동 문제 링크 어떻게 풀까? 굉장히 전형적인 bfs 문제입니다. 이 문제를 해결하기 위해서는 크게 세 가지의 생각이 필요합니다. 1. 인구 차이가 L명 이상, R명 미만인 인접한 국가를 묶어서 연합으로 만드는 방법2. 연합이 된 국가의 인구수를 바꾸는 방법3. 연합이 되는 국가가 없어서 수행을 종료하는 방법 일단 1, 2방법을 한 번에 묶을 수 있는 방법이 있습니다.바로 B.F.S입니다. 연합된 국가를 찾으려고 할 때마다, 2차원 배열을 모두 돌면서 인구차이가 L명 이상, R명 이하가 나는 국가를 모두 연합해서 큐에 넣습니다.그리고 큐에 들어갈때 마다 해당 국가의 인구수를 모두 더합니다. 이제 마지막에 모든 국가의 인구수와 큐에 들어있는 국가의 수를 나누면 균등하게 나눠진 인구 값이 나옵니다. 이제, 큐에서.. [삼성 기출 문제] 백준 14502 연구소 문제 링크 클릭시 이동합니다. 어떻게 풀까? 문제를 크게 2 부분으로 나눠야 합니다. 1. 벽을 3개 세우는 부분2. 바이러스를 퍼뜨리는 부분 1번은 dfs를 이용해서 조합을 이용해서 해당 좌표에 벽을 세운다 or 안세운다 의 동작을 통해서 모든 구역에 벽을 3개씩 세워보는 방법을 이용합니다. 그리고 벽을 3개 세웠을 때, bfs를 이용해서 2번을 동작해서, 바이러스의 개수를 세서 이 최댓값을 출력하면 풀이는 완료됩니다! 2차원에서 조합을 이용하는 방법을 알아봅시다! n = 3이라고 하겠습니다. 시작은 (0,0) 입니다.우선, (0,0)에 벽을 세울지 안 세울지 정합니다. 우선 세운다고 가정하겠습니다. 그럼, 열의 크기를 1 늘려준 뒤에 해당 위치에서 다시 위의 과정을 반복합니다.이번에는 안세운다고 하겠.. [삼성 기출 문제] 백준 13460 구슬 탈출 2 문제 링크 클릭시 문제로 이동합니다. 어떻게 풀까? 우선, 맵의 크기를 확인해 봅시다! 10 * 10의 맵의 크기를 가집니다. 그리고, 빨간 공과 파란공 2 가지 경우가 있죠. 그 말인 즉슨! 4 차원 배열을 통해서 [빨간공의 행][빨간공의 열][파란공의 행][파란공의 열] 형태로 visit 처리를 만들 수 있고,이를 통해 bfs를 이용하면 구슬을 빼낼 수 있는 최단 시간을 출력할 수 있습니다! 큐 에는 빨간공의 위치와 파란공의 위치를 넣으면 되겠죠! 10번이 넘어가면 -1을 return 하면 되겠군요! 그럼, 판을 상, 하, 좌, 우로 움직일 땐 어떻게 하면 될까요?그저 공의 위치를 저장해 놓고, 오른쪽으로 이동하면서 벽이 만나는 경우 그 전의 위치에다가 공을 위치시키기만 하면 됩니다!아래의 경우를 보.. [BOJ] 2206. 벽 부수고 이동하기 벽 부수고 이동하기 성공클릭시 이동합니다. 어떻게 풀까? 최단 경로를 구하기위해 단순한 BFS로 풀려고하면 약간의 오류가 생깁니다!바로, 벽을 부술수 있는가? 의 유무 때문이죠! 따라서, 벽을 부술수 있는지의 여부를 따로 저장하기 위해 visit 배열을 2개 사용합시다!이렇게 관리하면, 평범하게 BFS를 돌려서 만약, (n,m)에 도착하면, 그 때의 이동 횟수를 출력하면 바로 그것이 최소 거리 입니다! 사실, 이 문제는 이전에 포스팅했던 미로탈출 과 아주 유사합니다!만약, 잘 이해가 안되시면 해당 포스팅을 확인해 주세용!! 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354.. [BOJ] 5213. 과외맨 과외맨클릭시 이동합니다. 어떻게 풀까? 굉장히 힘들었습니다.우선, 문제의 절반이 별로 문제 푸는데 도움이 안된다는 사실에 좌절했습니다. 허허 이 문제는 BFS문제이지만, 단계를 잘 설정해서 수행해야 한다는 것이 중요합니다.문제를 풀기 위해서 생각해야 할 것들에 대해서 생각해 봅시다. 1. 타일들 간에 이동가능한 인접 행렬을 만들어야 합니다.2. BFS를 통해서 최단 거리를 찾습니다.3. 최단 거리를 찾는 경로를 어떻게 출력할지 생각해야 합니다. 이 중에서 가장 어려운 것은 1번 입니다. 타일을 어떻게 붙일지에 대해서 생각해 봅시다! 일단, 약간 귀찮은 점은 홀수행과 짝수행에서 타일의 개수가 다르다는 것입니다! 우선은, 타일을 모두 왼쪽으로 밀어넣어서 생각해봅시다!또한, 타일에 여러 정보가 있기 때문에 따.. [BOJ] 1219. 오민식의 고민 (18.8.22 그림 추가) 오민식의 고민클릭시 이동합니다. 어떻게 풀까? 으악... 저는 dfs와 bfs를 이용해서 풀었는데... 알고보니 벨만-포드 알고리즘이었어요.. 이따가 벨만-포드로 풀어서 해당 방법도 업데이트 하겠습니다. 버전 1과 2로 나누죠! Version.1 DFS and BFS 노드가 100개밖에 없으니 DFS를 이용해서 최댓값을 구해봅시다.잘 생각해보면, 해당 문제에서 양수 사이클이 생겨서 무한이 생기는 경우는, 방문했던 점을 또 방문할 경우에만 생깁니다.더 정확하게 말하면, 양수 사이클이 생겼을 경우이죠. 반대로, 음수 사이클이 생기는 경우에는 싸이클의 반복 경로를 탄다면, 가격이 계속 줄어든다는 것을 알 수 있죠!결국, 음수 사이클이 생기는 경우에는 반복 경로를 타지 않고 가는 것이 최대 수익을 얻는 경우입니.. 이전 1 2 다음
