그래프 (2) 썸네일형 리스트형 백준 3197, 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... ...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... ..XXXXX..XXXXXX.... 그래프(Graph), 넓이 우선 탐색(BFS), 깊이 우선 탐색(DFS) 그래프(Graph)는 각 정점(Vertex)와 간선(Edge)로 이루어진 자료구조이다. 그래프는 실생활에서도 많이 접할 수 있다. 버스 노선도, 지하철 노선도도 일종의 그래프이다. 그래프는 자료 구조 중에서도 가장 근본적인(?) 자료 구조라고 볼 수 있다. 그 예로 리스트(List)의 경우에도 구성을 보면 하나의 노드(Node)에 데이터와 다음 혹은 이전의 노드에 대한 정보를 저장하고 있어서 서로 연결되어 있다는 점에서 그래프의 정의라고 볼 수 있다. 트리 역시 루트 노드(Root Node)를 시작으로 밑에 자식 노드(Child Node)들이 연결되어 구성된다는 점에서 간선에서 제약 사항이 있는 그래프라고 볼 수 있다. 그래프를 표현하는 방식에는 인접행렬로 표현하는 것과 인접리스트로 표현하는 방식이 있다.. 이전 1 다음
