09 그래프 Graph 출처 C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저) 목차 그래프의 개념 1-1. 그래프란 1-2. 그래프의 종류 1-3. 네트워크 1-4. 그래프 용어 그래프의 표현방법 2-1. 인접행렬 방식 2-2. 인접리스트 방식 그래프의 탐색 3-1. 깊이 우선 탐색 DFS 3-2. 너비 우선 탐색 BFS 1. 그래프의 개념 1-1. 그래프란? 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료구조이다. 그래프의 예로는 지도에서 도시들의 연결상태, 전기회로의 소자 간 연결 상태, 도로망, 대학교 선수과목 관계 등이 있다. 트리도 일종의 그래프로 받아들여진다. 선형리스트, 트리로는 도시, 소자, 자원, 프로젝트 등의 객체들이 서로 연결되어 있는 복잡한 구조를 표현..
찾아라 프로그래밍 마에스터 문제 문제 풀러 바로가기 👇👇👇👇👇👇 https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 문제내용은 위 링크 참고바람 문제풀이 위 문제는 BFS(너비 우선 탐색)을 이용하면 아주 쉽게 풀 수 있는 문제이다. queue(deque 라이브러리 사용)를 이용해 지도의 좌표를 저장하고 차례대로 좌표를 꺼내 퍼트려나가면 된다. 방향은 위, 아..
백준 온라인저지 7576번 토마토 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제풀이 1. 바이러스같이 퍼져가는 구조이므로 bfs를 사용해야한다. 2. 퍼져나가면서 1씩 증가시켜 기록하면 최대값을 통해 모두 익을 때까지의 최소 날짜를 알 수 있다. 3. dx, dy 배열을 이용해 사방에 있는 토마토들을 탐색하자. 4. 만약 bfs를 사용해서 탐색했는데도 0이 남아있다면 -1에 의해 가로막혀 있는..
