본문 바로가기

분류 전체보기116

[Epper] 사다리(집으로 가는 길) 문제 겨울이와 친구들은 자신의 집으로 돌아가야 합니다. 겨울이 포함 4명의 사람이 있다고 했을 때, 현재 각 사람이 갈 수 있는 길은 그림1과 같습니다. 편의를 위해 사람에게 번호를 부여하였으며, 각 집에는 살고 있는 사람의 번호로 표시됩니다. 이런 도로상황에서, 우리는 강을 가로지르는 다리를 추가할 수도 하지 않을 수도 있습니다. 다리 추가 작업을 마친 후, 각 사람은 도로를 따라 목표지점인 본인 번호의 집까지 가야합니다. 1번사람을 예시로 들면, 아무런 다리가 설치되어 있 지 않을 경우, 3번집으로 가게 됩니다. 하지만 그림2 와 같은 다리가 놓여있을 경우라면, 모든 사람은 그림3처럼 빨간 경로를 따라 자신의 집에 도착하게 됩니다. 1번 사람은 1번 집, 2번사람은 2번 집, 3번 사람은 3번집, 4.. 2021. 9. 2.
[백준] DFS와 BFS - 2667번 단지번호붙이기 java 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고.. 2021. 8. 30.
[백준] DFS와 BFS - 2606번 바이러스 java 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 .. 2021. 8. 28.
[백준] DFS와 BFS - 1260번 DFS와 BFS java 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 풀이 DFS와 BFS의 기초를 익힐 수 있는 문제다. DFS란, 깊이 우선 탐색으로 하나의 노.. 2021. 8. 26.

티스토리툴바