반응형 BFS3 [삼성SW테스트] 백준 16234 인구이동(DFS) 백준 DFS 문제 #16234- 인구이동 https://www.acmicpc.net/problem/16234 사용한 개념 DFS 문제입니다. BFS로도 할 수 있을 것 같은데, 저는 DFS 재귀 연습도 할겸 DFS 했습니다. 연합을 이룰 수 있는 국가를 구하고, 연합 국가의 총 인구수와 국가를 나누는 간단한 DFS문제입니다. 제가 생각한 프로세스는 다음과 같습니다. 1. DFS로 조건에 맞는 연합국가를 구한다. 2. DFS탐색시 조건에 맞는 국가는 Sticker를 붙여서 연합국을 구별하도록 한다. 3. 각 연합국안에서 인구이동 실시. 4. 1-3 계속 반복...더이상 인구이동이 없을 때까지... 딱히 어려운건 아니였으나...시간차를 두고 풀어봤는데, 다르게 소스를 짰네요...ㅎㅎ.. 간혹 시간초과가 뜨는.. 2019. 3. 26. [BackJoon] 백준 3055 탈출(BFS) 백준 BFS 문제#3055- 탈출 https://www.acmicpc.net/problem/3055 사용한 개념 BFS개념을 사용했습니다.문제에서의 포인트는 다음과 같습니다. 한 단계씩 시간이 지날 때마다 고슴도치는 한칸 이동할 수 있고, 물은 상하좌우 4방향 중 물이 넘칠 수 있는 곳에 넘칩니다. 여기서 중요한 것은 물이 한단계 이후에 넘칠 위치는 고슴도치가 이동 할 수 없다는 것이 포인트 입니다. 자 아래 2가지만 명심하면 문제는 쉽습니다. 1. DFS를 통해 단계가 진행될 때, 고슴도치, 물 이 움직일 수 있는 조건들을 생각해 코딩합니다.2. 여기서 물이 한단계 이후 넘칠 공간에는 고슴도치가 이동할 수 없기 때문에 물을 먼저 넘치게하고 그다음! 고슴도치가 움직이는 매커니즘으로 작동하게 한다!! 여기.. 2019. 1. 7. [BackJoon] 백준 1697 숨바꼭질(BFS) 백준 BFS 문제 #1697- 숨바꼭질 https://www.acmicpc.net/problem/1697 사용한 개념 BFS개념를 응용했습니다. 우선 방문한 곳은 check 1차원 배열로 방문여부를 체크하여 방문하지 않은 곳만 방문을 하게끔 만들고, BFS 을 통해 방문하지 않은 곳을 계속해서 탐색하도록 합니다. 여기서 포인트는 방문할 때마다 몇번만에 해당 탐색지점에 왔는지 카운트를 해주는 것입니다. *2에서 5를 찾는 경우 예를 들어 2번에서 시작한다고 치고, 2번에서 *2를 해 4번으로 갔다면, 처음 2번에는 카운트 0을 저장하고 4번에 카운트는 0+1 = 1 입니다. 다음 4번에서 +1을 했다면 5번에는 카운트 0+1+1 = 2 입니다. 이런식으로 2에서 시작해 5번으로 도착할때 카운트는 결국 카운.. 2019. 1. 3. 이전 1 다음 반응형
