반응형 Algorithm/BackJoon25 [삼성SW테스트] 백준 16236 아기상어(BFS) 백준 BFS 문제#16236- 아기상어 https://www.acmicpc.net/problem/16236 사용한 개념 BFS개념을 사용했고, 문제 안에 있는 단계적인 스텝은 시뮬레이션으로 구현했습니다. 시뮬레이션이라고 하면, for문 if문 등 조건/반복문을 열심히...코딩해서 구현하는 것을 뜻합니다 ㅎㅎ...음..해당 문제에서 주어지는 요구사항을 저는 아래의 메커니즘으로 구현했습니다. 1. 먹을 수 있는 물고기를 전부 일괄 저장해논다!2. 먹을 수 있는 물고기들끼리 가장 먼저 우선해서 먹어야할 하나의 물고기만 선별! (선별조건은 문제에 있습니다.)3. 물고기 먹은 횟수 증가 및 나이를 증가해야하는지 여부 체크!4. 먹을 물고기 위치에서 다시 상어를 위치시키고, 1번 스텝 반복! 여기서 이동할 때 포인.. 2019. 2. 27. [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. [BackJoon] 백준 2606 바이러스(DFS) 백준 DFS 문제#2606 - 바이러스(Virus) https://www.acmicpc.net/problem/2606 사용한 개념 DFS깊이탐색을 이용했습니다.문제를 보면, 결국 무조건 1과 연결되어 있는 컴퓨터 갯수를 새는 것입니다. 컴퓨터 1과 연결되어 있으면 계속 깊이탐색을 해서 연결된 컴퓨터 갯수를 카운트하면 답은 쉽게 나옵니다. 컴퓨터 1과 연결되어있지 않는 또 다른 네트워크 영역은 신경쓸 필요도 없습니다. 따라서 소스에서 보면 알 수 있듯이 DFS(1)을 주어 무조건 시작은 1번 컴퓨터에서 시작함을 알 수 있습니다. DFS 기본 개념을 이해하면 쉽게 풀수있고 DFS를 잘 모르면, 어렵습니다.저는 기본적으로 인접리스트 방식의 DFS 깊이탐색을 했습니다.혹, DFS 기본개념을 모르시면 아래 링크에.. 2018. 12. 11. 이전 1 2 3 4 5 ··· 7 다음 반응형
