백준 문제 리뷰/그래프

문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 개요 어제 블로그에 다익스트라(Dijkstra) 알고리즘을 정리한 글을 작성했다. 그리고, 오늘 실제로 다익스트라를 활용한 문제를 풀어보고자 이 문제를 풀어보았다. 예전에는 다익스트라 코드를 무식하게 다 외우기만 해서 시간이 지나면 금방 휘발되었는데, 확실히 알고리즘 동작 과정을 세세하게 이해하면서 코드를 직접 작성하니까 실수 없이 다익스트라 코드..

문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 개요 처음 문제를 봤을 때 어떻게 구현해야 할지 감이 바로 오지 않았다. 10 x 10 크기의 100칸짜리 보드판이 주어졌기 때문에, 10 x 10 의 2차원 배열을 만들어야 하는 것인가 생각했다. 왜냐하면, 이 문제가 그래프 카테고리에 있었기 때문에 DFS 또는 BFS를 사용하는 문제일텐데, 궁극적으로 목적지까지의 최소 거리를 구하는 문제이므로..

문제 출처 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 구현 방법 1. 이차원 배열 형태의 input이 주어지고, 문제를 읽어보았을 때, DFS나 BFS와 같은 그래프 순회 알고리즘을 사용해야 한다는 것을 직관적으로 알 수 있다. 2. DFS를 사용할지, BFS를 사용할지 선택을 해야 한다. -> 단순히 시작점부터 도착점까지 그래프를 순회하는 유형의 문제에서는 DFS를 사용하든 BFS를 사용하든 상관 X (최단 거리가 보장되..