인접 행렬
-
[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 요구사항 - 창고에는 익은 토마토와 익지 않는 토마토가 있다. - 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받는다. - 하나의 토마토의 인접한 곳은 상하좌우를 의미한다. - 대각선 방향에 토마토는 영향을 받지 않는다. - 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. - 창고에 모든 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수를 구하라. 입력 첫 줄에는 상자의 크기를 나타내..
-
[그래프 탐색] 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 사이에 간선이 존..