BFS
-
[알고리즘] 너비 우선 탐색 (BFS, Breadth-First Search)Algorithm 2020. 12. 11. 19:13
너비 우선 탐색 (BFS, Breadth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 너비 우선 탐색은 현재 위치를 기준으로 사방으로 퍼져나가면서 탐색하는 방법으로, 인접한 정점들을 먼저 탐색한 후에 차례로 탐색을 진행한다. 장점 모든 가중치가 동일할 때, 시작 정점으로 부터 목표까지 최단 경로를 보장한다. 단점 정점의 수가 늘어날 수록 탐색에 불필요한 정점을 저장해야 하기 때문에 저장공간이 비교적 많이 필요하다. 주로 두 정점 사이의 최단 경로나 임의의 경로를 찾을 때 사용한다. 점점 탐색 범위를 확장하며 탐색하기 때문에 처음 발견하는 경로가 최단 경로가 된다. 주의할 점은 DFS와 마찬가지로 방문 체크가 필요하다. 그림으로 이해하면 쉽기 ..
-
[백준 13459 - JAVA] 구슬 탈출Algorithm 2020. 11. 17. 18:20
13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드를 기울이면 구슬이 끝까지 이동하는데, 구슬이 겹치는 상황에서 어떤 구슬이 앞쪽에 있는지만 신경쓰면 크게 어렵지 않은 문제! 풀이 방법 빨간 구슬의 위치와 파란 구슬의 위치를 갖고 있는 클래스를 구현한다. (1차원 배열로 해도 될것 같다.) 네 방향으로 기울여서 이동한 위치를 확인한다. move 메소드에서 처음 빨간 구슬의 위치가 앞인지 먼저 체크를 해준다. 빨간 구슬과 파란 구슬을 벽이 나올때까지 혹은 구멍에 ..
-
[백준 1261 - JAVA] 알고스팟Algorithm 2020. 11. 9. 19:13
1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 방향을 맞게 잡았으나 조건을 잘못 넣어서 메모리 초과가 2번 났었다. 다익스트라인줄 몰랐으나 풀고보니 최소 횟수를 따라가며 갱신할 수 있을 때 큐에 삽입하는 다익스트라 방식으로 잘 풀었었다ㅎㅎ... 풀이 방법 벽을 뚫은 횟수(이하 cnt)를 저장할 2차원 배열(ans) 을 생성하고 큰값으로 초기화한다. 초기 장소인 0, 0 cnt는 0으로 배열을 만들어 cnt가 기준인 우선순위큐에 넣는다. * 처음 장소는 항상 뚫려있다. 큐가 빌때까지..
-
[SWEA 4193 - JAVA] 수영대회 결승전Algorithm 2020. 11. 9. 18:25
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성이를 우승시키기위한 최단 경로의 시간을 출력하자! 신호등 문제로 BFS에 현재시간과 소용돌이를 건널 수 있는 시간을 비교해서 큐에 넣어준다. 소용돌이의 시간이 일정하기 때문에 신호등이나 견우와직녀보다는 비교적 쉬운 문제다. 풀이 방법 시작점을 큐에 넣어준다. 큐 사이즈를 받아서 사이즈 만큼 돌아준다 (시간 체크) 소용돌이를 만날 경우 건널 수 없으면 다시 큐에 넣어준다. 2번을 체크해서 BFS를 구현할 경우 visit배열을 int형으로 해줄 필요가 없다 (메모이제이션 불필요) import java.io.*; import java.util.*; public cl..
-
[백준 1726 - JAVA] 로봇Algorithm 2020. 11. 9. 18:22
1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력하자! 아래 사항과 방문 처리만 주의한다면 문제없이 풀 수 있다. 방향이 동서남북 순서 시작점과 도착점이 같을 수 있다 -> 그러면 답이 0 2칸 이상 이동시 이동중 벽을 만날 경우 이동할 수 없다. 풀이 방법 입력받는 시작, 도착 위치가 1부터 이기때문에 1을 빼준뒤 저장한다. 시작점을 넣고 BFS를 시작하고, 방문 배열은 위치에 방향을 포함하여 3차원으로 처리한다. 이동 명령 먼저 수행하고, ..
-
[백준 9019 - JAVA] DSLRAlgorithm 2020. 11. 9. 18:19
9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 숫자A에서 숫자B로 변환하기 위해 필요한 최소한의 명령어 나열을 구하자! bfs에 대한 개념을 잘 잡고 있다면 간단하게 풀 수 있다. 제출 후 정답율이 올라가는게 삐끄덕 거리면서 느려서 당황했지만 무사히 통과! ✧ʕ̢̣̣̣̣̩̩̩̩·͡˔·ོɁ̡̣̣̣̣̩̩̩̩✧ 풀이 방법 숫자와 문자열을 가진 Number클래스를 이용해 bfs를 수행한다. 큐에 숫자A를 넣고 시작한다. DSLR을 순차적으로 실행 후, 숫자를 비교하여 숫자B와 같을 경우 문자열을 반환한..
-
[SWEA 4727 - JAVA] 견우와 직녀Algorithm 2020. 11. 9. 18:12
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 견우가 까마귀와 까치의 도움으로 최대한 빠르게 직녀에게 가는 방법을 찾아내자! BFS에 여러가지 조건을 적용한 문제로, 예전에 풀었던 신호등과 비슷한 문제다. 신호등은 추후에 업로드시 링크를 달아야겠다! 문제를 읽기가 힘들고, 조건을 이해하는게 힘들었다…. 풀이 방법 BFS를 돌면서 아래의 조건을 만족시킨다. 방문처리는 메모이제이션으로 가장 짧은 시간을 저장하여 확인한다. 오작교는 시간이 T라면 T의 배수에 건널 수 있다. 견우는 절벽을 연속으로 건널 수 없다. 교차하는 곳에는 오작교를 만들 수 없다. 0인 곳 (M인 오작교)는 한 개만 만들 수 있다. impor..