목록Algorithms/BFS (12)
혼종 꼬지마루
이것 또한 삼성전자 기출이라고 한다 그냥 BFS라고 생각해서 풀었다가 예외처리를 겁나 해준..... dfs와 함께 섞어서 사용하지만, 메인은 bfs라서 bfs에 올림 최적화나 코드 정리따위는 하고 싶지않아서 그냥 간단하게 코드정리만 하고 포스팅 1. 언제나 그렇든 map을 입력을 받는다- 입력을 받으며 바이러스는 따로 구조체배열에 저장하고, 벽과 바이러스가 없는 구간의 공간을 count해준다 2. dfs를 돌면서 virus를 M개만큼 선택하며 큐에 담아준다 3. bfs에 들어가면, 큐에 담긴 K개의 좌표를 visit배열에 표기하고, st값을 올려주면서 virus(순회한 virus로 정의했음)의 갯수를 올림 4. bfs를 돌면서 조건에 맞게 단순 bfs를 돌지만, virus가 있는 공간을 지날때, map[..
생각보다 시간이 오래 안걸렸던 문제... 디버깅하느라 시간 오래 쓴줄 알았는데 1시간도 안걸렸다 그냥 문제 조건에 맞게 BFS만 잘 던져주면 쓕하고 풀리는 문제였다. 2. 단지 번호 붙이기 처럼 입력된 조건 범위 내에 차이가 나는 국가들을 BFS로 찾으면서 그 값을 더하고, 갯수를 센다. 3. 함수 종료 전, 찾은 국가들은 check배열에 모두 더한 숫자 / 국가 숫자 로 나누어 갱신 4. map이 check배열과 똑같다면 인구 이동이 없었던 것으로 간주하여 while문 탈출, 아니라면 map을 check배열로 갱신하고, 동시에 check배열을 초기화 이 과정만 잘 구현해 준다면 문제 없이 풀리는 문제이다. 123456789101112131415161718192021222324252627282930313..
이 문제를 풀면서 거의 두 시간정도 아기상어 노래를 부른거 같닼ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 문제를 이해하고 구현하는데 1시간 걸렸는데.... 풀고보니 내가 이해한건 90퍼 였다 나머지 10퍼는 디버깅하면서 찾느라 30분 정도 걸림.... 자 문제의 조건에 대해서 생각하며 BFS탐색과 메모이제이션?이라고 해야하나...만족하는 값을 저장하고 갱신하는 방법으로 진행했다. 1. BFS탐색을 통해 최단거리 내의(맨위, 맨 왼쪽->문제의 조건을 만족하는 지점)의 갈 수 있는 곳을 찾는다. 2. 찾았다면 갈 수 있는 지점이라 판단, list에 저장한다. 3. 계속 BFS 탐색이 종료되면 문제의 조건에 맞게 sort한다. 4. 저장된 list[0].dis를 리턴함으로서 거리를 더해 주고, 그 위치를 map에서 삭제한다. 5. 먹..
일단 이 문제는 DFS, BFS 둘 다 가능하지만, 저는 BFS를 선호하기 때문에 BFS로 풀었습니다 1. 입력된 맵정보를 2차원 for문으로 순회하면서 맵이 1인 부분에서 BFS로 영역을 탐색 2. BFS 탐색이 한번 끝날 때 마다 카운트를 올려주면서 영역의 갯수를 구해주면 끝 ICT코테는 영역의 넓이를 구하라고 되어 있는데 이것도 BFS 내부에서 마킹할 때 마다 카운트를 세주면 되는 간단한 문제! 그래도 혹시 모르니 DFS, BFS문제 모두 올리겠습니다 - BFS버전 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#in..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4(문제가 될 시 삭제하도록 하겠습니다.) D5이긴 한데 그렇게 어렵지는 않았던문제... 그냥 문제를 잘 못 이해해서 좀 뻘짓했음 게다가 BFS라기도 뭐하고...시뮬레이션에 BFS조금 섞은 느낌 1. 상원이의 친구를 일단 큐에 넣으며 초대장을 나눠주는 갯수를 센다. 2. 큐에서 하나씩 빼며 그 친구의 친구를 중복되지 않도록 초대장을 나눠준다. 이때 큐에 다시 집어넣지 않도록 조심! 3. 초대장을 나눠준 갯수를 리턴 12345678910111213141516171819202122232425262728293031323334353637383..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN(이 문제 포스팅이 문제가 될 시 삭제하겠습니다) 이 문제의 핵심은 '이 일을 하고 다음에 해야할 일'과 '이 일을 하기 위해서 이전에 해야할 일'로 나눠줘야 합니다. 이 두가지를 핵심으로 나눈다면, 그다음엔 간단한 BFS로 해결 가능! 즉, BFS+ 그래프 문제 입력을 받음과 동시에 '이 일을 하고 다음에 해야할 일'과 '이 일을 하기 위해서 이전에 해야할 일'을 그래프로 만들어 구분 일의 시작점에서는 '이 일을 하기 위해서 이전에 해야할 일'이 없으므로 이 지점을 모두 큐에 담아줍니다. 그리고 나서 큐에서 빠져 나올때 '일을 했다..
그냥 문제에 조건에 맞게 BFS만 잘 구현해주면 될 것 같았던 문제 하지만 visit을 체크하는 과정에서 통나무의 방향을 따로 체크해줘야 하기 때문에 3차원 check배열이 필요했다 그 외에는 문제의 조건에 맞게만 구현해주고, 3개를 한꺼번에 움직이는 것이 귀찮을 뿐 그냥 저냥 할만했던 문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114..
BFS를 총 4번던져서 풀수 있는 문제 이 문제도 stl을 사용하면 풀 수 없다고 생각 그리고....다시 풀어보라하면 절대 풀지 않을 문제.... 문제는 되게 간단해보이게 짧게 나오지만, 개인적으로 구현이 제대로 안되서 한 20번은 넘게 틀린 것 같다 1. 먼저 A를 연결 시켜본다. BFS를 던져서 두 점이 연결되는 지점이 오면 역추적해서 그 경로에 마킹 이때 B의 양 끝점은 비켜가도록 조심해야한다(이것 때문에 한 10번은 틀림...) 2. A의 연결점이 마킹되어 있는 상태에서 B를 BFS로 연결시킨다. 이 두개가 연결이 된다면, A의 최단길이, B의 최단길이를 더한다. 3. 위의 방법을 B->A순으로 한 번 더 해준다. 이렇게 총 2번의 연결을 통해 나온 답 중 최단의 것을 사용 연결할 수 없다면 IM..
이 문제는 bfs + 비트마스킹을 이용한 문제 다만, 열쇠를 찾았을때, 지나온 곳에 그 문이 있을때 어떻게 처리해줘야 할지가 가장 중요합니다 제가 사용한 방법은, 열쇠가 없는 문을 만났을 때 다른 구조체 배열에 위치와 문의 알파벳을 저장 열쇠를 찾는다면, 찾은 열쇠로 열 수 있는 문(열쇠가 없는 문을 저장해 구조체배열)을 찾아서 다시 큐에 담아줍니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #define MX 110using namespa..
BFS + 그래프를 이용하여 해결 가능 다시 풀기 싫은 문제... 다른방법이 있을지는 모르겠지만 개인적으로는 stl을 사용하여 Queue를 사용하면 못풀 것 같다는 생각이 드는 문제 배열을 2칸을 묶어서 1칸으로 쓰는 것도 중요하다 1. 입력을 받고, 배열 2칸을 1칸으로 만들어 문제와 똑같은 형태로 각 칸에 번호를 매긴다 2. 각 정점에서 문제 조건에 맞는 갈 수 있는 방향을 그래프로 만들어 준다. 3. 이 그래프를 시작으로 BFS탐색 시작! 4. 문제의 조건 중 '도착할 수 없다면 가장 큰 위치로 이동한다'이 조건을 위해 번호가 크다면 계속 갱신을 시켜주고, 이 경로를 추적하기 위해 큐에 들어가는 정보 중 이전 큐의 위치, 즉 탐색을 하는 위치의 큐넘버를 함께 담아준다 5. 문제의 조건에 맞게 출력!..