본문 바로가기

알고리즘/백준

 (40)
[백준 1697 : JAVA] 숨바꼭질 / BFS 개요 BFS는 최단거리를 구하는 경우 가중치가 1일 때 사용할 수 있다. 이 문제는 동생과 형의 시작 지점이 같을 경우 반례 때문에 삽질 좀 했다. 자신 스스로 반례를 찾는 습관을 가지는 것을 추천한다! 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 풀이 1. 형의..
[백준 7569 : JAVA] 토마토 / BFS 개요 이 문제는 아래의 문제에서 배열만 3차원 배열로 변경된 문제이다. 아래 문제를 풀고 이 문제를 접근하면 쉽게 풀이할 수 있을 것이다. 2020/02/09 - [알고리즘/백준] - [백준 7576 : JAVA] 토마토 / BFS [백준 7576 : JAVA] 토마토 / BFS 개요 BFS와 DFS는 탐색 알고리즘이다. 둘 중 어떤 알고리즘을 선택할 것인지 선택해야 할 때 나는 보통 둘이 탐색하는 모양을 생각해본다. DFS는 한 노드에 도달 했을 때 갈 수 있는 노드가 있는 경우 끝까지 찾고.. dragon-h.tistory.com 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서..
[백준 7576 : JAVA] 토마토 / BFS 개요 BFS와 DFS는 탐색 알고리즘이다. 둘 중 어떤 알고리즘을 선택할 것인지 선택해야 할 때 나는 보통 둘이 탐색하는 모양을 생각해본다. DFS는 한 노드에 도달 했을 때 갈 수 있는 노드가 있는 경우 끝까지 찾고 돌아오고, BFS는 물의 파장처럼 점진적으로 퍼지며 탐색을 진행한다. 따라서 이문제는 익은 토마토 중심으로 점진적으로 퍼저나가며 토마토를 익게 만들기 때문에 BFS를 선택한다. 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익..
[백준 2178 : JAVA] 미로탐색 / DFS BFS 특징 개요 DFS Stack 혹은 재귀함수(Recursion)으로 구현된다. 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행 모든 노드를 방문하는 경우에 이 방법을 사용한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) BFS Queue를 사용해서 구현한다. 시간 복잡도 인접 리스트 : O(V + E) 인접 행렬 : O(V^2) BFS는 다음의 경우 효과적으로 풀이할 수 있다. 1. 최소 비용 문제 2. 간선의 가중치가 1인 경우 3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족한다.) 이 문제는 1번째 조건과 최단거리 조건이 만족 때문에 DFS로 풀이하면 시간초과가 나게된다... DFS로 ..
[백준 1012 : JAVA] 유기농 배추 / DFS 개요 기본적인 DFS, BFS를 통해 단절된 구역의 개수를 구하는 문제이다. 이 문제는 다음 문제와 비슷하며 이 문제를 먼저 풀고 다음 문제를 풀어보길 추천한다. 이 문제에서 약간 추가된 부분이 있는 문제이다. 2020/01/30 - [알고리즘/백준] - [백준 2667 : JAVA] 단지번호붙이기 / DFS [백준 2667 : JAVA] 단지번호붙이기 / DFS 개요 dfs를 이용하여 을 의 형태의 배열로 만든다. 단절되어 있는 단지들의 집의 개수를 구하면 된다. dfs를 통해 한 노드에서 갈 수 있는 노드 모두를 탐색하면서 풀이한다. 문제 과 같.. dragon-h.tistory.com 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 ..
[백준 2667 : JAVA] 단지번호붙이기 / DFS 개요 dfs를 이용하여 을 의 형태의 배열로 만든다. 단절되어 있는 단지들의 집의 개수를 구하면 된다. dfs를 통해 한 노드에서 갈 수 있는 노드 모두를 탐색하면서 풀이한다. 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 풀이 DFS를 이용한다. dfs(int x..
[백준 2606 : JAVA] 바이러스 / BFS 개요 이 문제는 dfs와 bfs 알고리즘 둘 다 풀이가 가능하다. 두 알고리즘에 대해 기본을 익히고 싶다면 아래의 문제를 먼저 푸는 것을 추천한다. 2020/01/30 - [알고리즘/백준] - [백준 1260 : JAVA] DFS와 BFS / DFS, BFS [백준 1260 : JAVA] DFS와 BFS / DFS, BFS 개요 dfs와 bfs는 둘타 탐색을 하는데 사용된다. dfs는 깊이 우선 탐색으로 스택 또는 재귀함수를 구현한다. bfs는 너비 우선 탐색으로 큐로 구현한다. (예전에 bfs를 처음 배울 때 물에 돌을 떨어 뜨렸을 때 파장.. dragon-h.tistory.com 갈 수 있는 모든 노드의 개수를 구하면 풀이가 가능하다. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한..
[백준 1260 : JAVA] DFS와 BFS / DFS, BFS 개요 dfs와 bfs는 둘타 탐색을 하는데 사용된다. dfs는 깊이 우선 탐색으로 스택 또는 재귀함수를 구현한다. bfs는 너비 우선 탐색으로 큐로 구현한다. (예전에 bfs를 처음 배울 때 물에 돌을 떨어 뜨렸을 때 파장과 같이 점차적으로 모든 방향을 동시에 탐색하고 나간다고 배웠는데 아직도 기억에 남는다...) 뭐 삼성 코테에서 주를 이루고 있는 문제라고 할 수 있다. 물론 난이도는 이문제보다는 높은 문제들이 많다.. 이 문제는 dfs, bfs 두 가지 방식으로 풀 수 있다는 것을 보여주고 있다. 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 ..

티스토리툴바