반응형 Algorithm/BFS16 [BFS] 거리두기 확인하기 - 2021 카카오 채용연계형 인턴십 해결 방법 맨해튼 거리의 개념을 모르더라도 단순히 BFS 알고리즘으로 해결할 수 있다. 자신을 제외한 응시자들 중에서 BFS 거리가 2이하인 응시자가 있다면 거리두기를 준수하지 않은 것으로 판단하면 된다. 주의할 점이 있다면 이 문제는 테스트케이스 5개가 있기 때문에 queue와 방문 배열을 초기화하는 작업이 필요하다. 그리고 연산 횟수를 줄이기 위해 거리두기 준수 여부를 나타내는 변수를 활용하여 거리 두기를 준수하지 않다는 사실이 확정났다면 해당 케이스에 대해서는 추가적인 연산을 수행하지 않도록 했다. 또, BFS 깊이가 3을 넘어가는 경우에는 queue에 구조체를 넣지 않았다. 소스 코드 #include #include #include #include using namespace std; struct.. 2022. 5. 17. [BFS] 배달 - Summer/Winter Coding(~2018) 제대로 동작하도록 구현하는건 쉽지만 시간 초과에 막힐 수 있는 문제다. 이 문제는 최대한 효율적으로 구현해야 한다. 해결 방법 필자는 BFS로 해결했다. Step1) 이 문제는 인접한 두 노드를 연결하는 간선이 여러개가 있을 수 있다. 그래서 인접한 두 노드를 연결하는 최소 비용의 간선들을 저장해둬야 한다. Step2) 노드와 간선을 연결한다. Step3) BFS를 수행하면서 1번 노드(마을)로부터의 최소 비용(시간)이 갱신된 노드만 Queue에 넣는다. 참고로, 갱신된 노드의 비용이 K를 넘어가는 경우에는 굳이 Queue에 넣지 않도록 처리하면 처리시간을 단축할 수 있다. Step4) 1번 노드로부터의 최소 비용이 K 이하인 노드를 모두 카운트한다. 단, 1번 노드는 당연히 카운트 해야하고, BFS를 .. 2022. 4. 15. [BFS] 블록 이동하기 - 2020 카카오 블라인드 채용 물체가 보드의 2칸을 차지하는 유형의 BFS 문제다. BFS 문제들 중에서는 꽤 난이도가 있는 문제였던 것 같다. 해결 방법 2x1 크기를 차지하는 로봇에 대한 구조체를 {좌표1, 좌표2, BFS 깊이}로 구성하여 생성했다. 이렇게 좌표 2개를 동시에 따지면 로봇이 가로로 서있는지, 세로로 서있는지, 어느 방향으로 서있는지 고려할 필요 없다. 또 BFS에서 방문 여부를 검사할 때도 좌표 2개를 동시에 따져야 한다. 그래서 방문 배열을 사용하지 않고, 두 좌표를 pair로 저장하는 벡터에 저장했다. 로봇이 움직일 수 있는 경우는 크게 3개로 나뉜다. 1) 회전하지 않고 상하좌우로 이동하는 경우 2) 좌표1을 기준으로 회전하는 경우 3) 좌표2를 기준으로 회전하는 경우 좌표1, 좌표2 둘 중 하나라도 벽과 .. 2022. 3. 18. [BFS, 난이도 중하] 프로그래머즈, 네트워크 BFS를 돌며 연결된 간선은 모두 방문 처리를 해주고, 더 이상 방문할 노드가 없을 경우 중단 한다. 모든 컴퓨터를 탐색하면서, 아직 방문하지 않은 컴퓨터일 경우 BFS를 시작해주고, BFS를 새로 시작할 때마다 answer를 1씩 증가시키면 문제가 해결된다. 한번 BFS를 수행하면, BFS의 시작점 컴퓨터와 같은 네트워크안에 있는 모든 컴퓨터가 방문처리 되는 것이다. 즉, answer = BFS 수행 횟수 가 되는 것이다. 테스트 케이스 13개 모두 통과 #include #include using namespace std; bool visited[201]; vector a[201]; queue q; void bfs() { while(!q.empty()){ int x = q.front(); for(int.. 2020. 9. 29. [BFS, 난이도 중상] 백준 2146번 다리 만들기 본인은 두 Step으로 나눠서 문제를 해결하였다. 큐는 각각 q,q2 이라는 이름의 큐 총 2개를 사용하였다. Step1에서는 q를 이용해 아래 그림과 같이 나라별로 숫자로 분류하였다. Step2에서 BFS를 수행하면서 어떤 나라를 만났을 때, 그게 자신의 나라인지 남의 나라인지 구별하는 과정을 거칠 것이기 때문이다. 이 과정 때문에 개인적으로 이 문제의 난이도는 중상으로 평가한다. Step2에서는 q2로 모든 지도를 탐색하여 방문하지 않은 바다 좌표를 만날 때마다 큐에 넣고, 방문 처리를 한다. 만약 탐색한 나라가 출발한 나라와 다를 경우, 구조체 node 에서 다리의 길이를 의미하는 depth 를 found 변수에 넣고 최솟값을 업데이트 해나갔다. g -> 나라 번호 depth -> 다리 깊이 x,y.. 2020. 8. 13. [BFS, 난이도 중] 백준 14502번 연구소 내 접근 법은 연구실 지도에서 빈칸인 좌표를 모두 v벡터 안에 넣고 벽을 세울 3곳의 좌표를 고르는 모든 경우의 수를 탐색하는 것이다. 브루트포스와 짬뽕인 문제인것같다. 지도의 크기가 최대 8x8 이라 순열을 이용하여 모두 탐색해도 시간 초과는 나지 않는다. 모든 케이스마다 casemap 배열을 초기 map과 같게 해주고 바이러스가 들어있는 좌표를 모은 큐도 다시 채워줘야 한다. a=v.size()-3 b=v.size()-2 c=v.size()-1 일 때는 모든 경우를 탐색했다는 뜻이므로 break문으로 빠져나와서, 안전 구역의 넓이의 최댓값을 출력하면 된 문제가 해결된다. #include #include #include #include #include #include #include using name.. 2020. 8. 11. [BFS, 난이도 중하] 백준 2468번 안전 영역 Case(물에 잠기는 최대 높이)별로 안전 지역이 모두 다르기 때문에 casemap이라는 임시 배열을 두었다. map배열의 각각 요소에 물에 잠기는 최대 높이를 빼준 배열이 casemap이 된다. 즉 casemap배열의 요소가 1이상이면 그 좌표는 안전 영역이 되는 것이다. 이 casemap 배열로 BFS를 수행하여 while문을 탈출할 때마다 group변수에 1을 추가하여 몇 개의 안전 영역 그룹이 생기는지 계산한다. 물에 잠기는 최대 높이를 1부터 99까지 99가지 경우에 대해 탐색하여 케이스별 group을 구해내면 된다. 케이스가 종료 될 때마다 ans의 최댓값을 업데이트 해나가며, 모든 케이스를 다 탐색 했을 때 최종 ans 값이 이 문제의 해답이 된다. #include #include #incl.. 2020. 8. 11. [BFS, 난이도 상] 백준 2206번 벽 부수고 이동하기 정답율 23%의 다소 까다로운편인 문제이다. 아무리 고민해도 해결하지 못한 비슷한 유형의 문제가 있었다. 그 문제는 백준 13460번의 구슬 탈출2 이였다. 주어진 예제는 다 돌아가는데.. 반례가 생기고 그 반례까지 돌아가게 하니 또 다른 반례가 생기고... 나 자신과의 혈전이었다. 구슬 탈출 2의 해결법이 정말 궁금했던 나는 Google Chance를 썼다. 이 유형의 문제는 구조체 와 모든 방문경우 를 다뤄야 한다는 사실을 깨닫고 내가 깨달은 해당 유형의 문제 풀이법을 4줄 요약해보았다. 한 map 안에 여러 물체가 동시에 움직여야 하는 경우 구조체 이용 2개 이상의 물체가 겹칠 수 없는 경우의 처리 -> 겹침의 여부에 상관없이 일단 논리적으로 모두 이동시켜놓은 후에 조건에 맞게 2차 처리 수행 노드.. 2020. 8. 10. [BFS, 난이도 중상] 백준 2573번 빙산 지금까지 BFS를 풀어왔듯이 빙산이 몇 개의 덩어리로 되어있는지는 bfs의 while문이 끝날 때마다 1씩 추가하는 group변수의 최종 값으로 알 수 있다. bfs의 while문을 다 돌았다는 것은 덩어리 하나를 모두 방문했다는 의미다. BFS를 수행하기 전에 빙산이 녹을 때마다 즉, 1년마다 빙산이 녹은 상태로 map배열을 바꿔주어야 한다. 문제 해결 흐름은 1. map배열입력 2. 1년이 지난 후의 빙산상태로 map배열을 업데이트 3. BFS로 몇 덩어리인가 계산 4. 여전히 1덩어리일 경우 과정2번으로 이동, 2덩어리 이상일 경우 정답 출력 이런 흐름으로 이루어 진다. adjacent 배열은 주변에 인접한 바닷물칸의 수를 나타내는 배열이다. map 배열에서 빙산의 높이가 0보다 작아졌을 경우에는 .. 2020. 8. 10. 이전 1 2 다음
