BFS
-
[Baekjoon Online Judge] 1012번: 유기농 배추문제 풀이/Baekjoon Online Judge 2021. 1. 17. 22:35
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 요구사항 - 해충 방지에 효과적인 배추흰지렁이를 구입한다. - 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹으며 배추를 보호한다. - 어떤 배추에 배추흰지렁이가 한마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있다. - 한 배추의 상하좌우 네 방향에 다른 배추가 인접한 배추이다. - 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 된다. - 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다. 입력 입력의 첫 줄에는 테..
-
[Baekjoon Online Judge] 2606번: 바이러스문제 풀이/Baekjoon Online Judge 2021. 1. 14. 14:55
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 요구사항 - 바이러스는 네트워크를 통해 전파된다. - 한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워크 상에 연결되어 있는 모든 컴퓨터는 바이러스에 걸린다. 입력 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. 출력 1..
-
[Baekjoon Online Judge] 7576번: 토마토문제 풀이/Baekjoon Online Judge 2021. 1. 14. 14:43
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 요구사항 - 창고에는 익은 토마토와 익지 않는 토마토가 있다. - 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받는다. - 하나의 토마토의 인접한 곳은 상하좌우를 의미한다. - 대각선 방향에 토마토는 영향을 받지 않는다. - 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. - 창고에 모든 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수를 구하라. 입력 첫 줄에는 상자의 크기를 나타내..
-
[Baekjoon Online Judge] 2667번: 단자번호붙이기문제 풀이/Baekjoon Online Judge 2021. 1. 13. 22:26
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 요구사항 - 1은 집이 있는 곳, 0은 집이 없는 곳을 나타낸다. - 집의 모임인 단지를 정의한다. - 단지에 번호를 붙인다. - 단지가 연결되었다는 것은 상하좌우에 다른 집이 있는 경우이다. - 대각선 상에 집은 연결된 것이 아니다. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내..
-
[Baekjoon Online Judge] 2178번: 미로 탐색문제 풀이/Baekjoon Online Judge 2021. 1. 12. 22:43
2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [그래프 탐색] DFS와 BFS 1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 hyeonic.tistory.com N x M 크기의 배열로 표현된 미로가 있다. 요구사항 1. 1은 이동할 수 있는 칸을 나타낸다. 0은 이동할 수 없는 칸을 나타낸다. 2. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸..
-
[Baekjoon Online Judge] 1260번: DFS와 BFS문제 풀이/Baekjoon Online Judge 2021. 1. 12. 22:32
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [그래프 탐색] DFS와 BFS 1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 hyeonic.tistory.com 간선을 연결하는 두 정점의 번호를 입력 받아 그래프를 그리고 DFS와 BFS로 탐색한다. DFS와 BFS에 대한 설명은 https://hyeonic.t..
-
[그래프 탐색] DFS와 BFS문제 풀이/Baekjoon Online Judge 2021. 1. 12. 20:31
1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 경우 방향을 가진 간선으로 나타낼 수 있다. 이때 이러한 그래프를 방향을 가진 그래프 혹은 Direct Graph 유향 그래프라고 한다. 반면 간선의 방향이 없는 그래프를 무방향 그래프 혹은 Undirected Graph 무향 그래프라고 한다. 2. 그래프의 표현 그래프의 표현 방법에는 행렬을 이용하는 방식과 리스트를 이용하는 방식이 있다. 2.1 인접 행렬 그래프 G = (V, E)에서 정점의 총 수를 n이라고 가정하자. 행렬의 크기는 n x n 행렬이 된다. 정점 i와 정점 j 사이에 간선이 존..