728x90 반응형 BFS5 [algorithm] 백준 - 아기상어 이 문제는 삼성 SW 기출 문제이다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 1. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 2. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 물고기를 잡아먹는 시간을 최소로 해야하므로 bfs로 탐색했다. 가장 위에 있고 가장 왼쪽에 있는 물고기를 먹어야하므로, bfs로 탐색을 한 후 가장 위에 있고 가장 왼쪽에 있는 물고기를 찾아 그 칸으로 이동시킨다. 탐색은 더이상 먹을 물고기가 없을 때까지 반복한다. while(1){ bfs.. 2020. 12. 28. [algorithm] 백준 - 로봇 청소기 이 문제는 시뮬레이션, bfs문제이다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다. 우선 왼쪽 방향으로 전진하는 함수, 후진하는 함수를 따로 작성해뒀다.. 2020. 12. 22. [algorithm] 백준 - 구슬탈출(2) 이 문제는 삼성 SW 기출 문제이다. 빨간 구슬을 구멍을 통해 빼내기 위해 기울이는 최소 횟수를 구해야 하므로 BFS로 풀었다. 문제에서 지켜야하는 조건이 있다. 1. 빨간 구슬과 파란 구슬이 같이 들어가면 실패 2. 빨간 구슬이 파란 구슬보다 먼저 들어가야 함 빨간 구슬과 파란 구슬을 이동하는 방향을 동일하게 설정해야하므로 방문 여부를 판단하는 배열의 인덱스도 빨간 구슬과 파란 구슬 모두의 방문유무를 설정해야한다. 이 방문 배열을 만드는 것을 생각하는 것이 가장 핵심이다. 그리고 큐에 넣을 때도 빨간 구슬과 파란 구슬의 위치, depth를 push해야한다. 따로따로 탐색하는 것이 아니라 같이 탐색해야한다! 참고로 중력에 의해 구슬의 위치가 정해지는데, ##### #..R# #...# #O.B# ####.. 2020. 12. 18. [algorithm] 백준 - 숨바꼭질 2 이 문제는 숨바꼭질 문제와 이어지는 bfs 문제이다. 추가되는 부분은 가장 빠른 시간으로 찾는 방법이 몇가지인지 구해야한다는 것이다. 예를 들어 수빈이는 1 에 위치해 있고 동생은 4에 있다고 가정하면, 가장 빠른 시간으로 찾기 위해선 여러 경우로 가지가 뻗어나갈 때, 동일한 시간에 두가지 방법이 있다는 것을 알 수 있다. 만일 queue에 값을 넣을 때 방문여부를 체크하게 된다면 1+1이나 1*2 중 가장 먼저 값이 넣어지는 경우의 방법만 찾을 수 있게 된다. 그러므로, queue에 값을 넣을 때 방문여부를 체크하지 말아야한다. 그렇다고 모든 방문 여부를 체크하지 말아야할까? 아니다, 방문 여부는 반드시 체크해야한다. 그러지 않으면 숨바꼭질은 끝나지 않는다. 그럼 방문 여부는 언제 체크해야할까? 최소 .. 2020. 11. 17. 이전 1 2 다음 728x90 반응형
