16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제를 풀면서 어떻게 BFS를 통해서 최소 탐색을 할 지 고민을 했습니다. 그래서 1~6을 추가해가면서 100이 되는 것을 확인해야한다고 생각했는데, 어떻게 풀어 나갈지가 가장 문제였다. 기존과 비슷하게 BFS를 진행하고, 각 경우의 수를 나누어 풀어나갔다. import sys from collections import deque input = sys.stdin.readline def bfs(start): q = ..
7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 앞에서 풀었던 토마토 문제와 같은 방법으로 BFS를 사용해서 풀면 쉽게 풀 수 있었다. 대신 2차원이 아닌 3차원 배열이라서 H의 값을 더 추가해서 풀었다. 코드는 앞에서 풀었던 BFS와 똑같지만 matrix의 차원만 하나 더 추가된 방법으로 풀었다. 그래서 쉽게 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(1, 0, 0..
7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 처음 이문제를 풀었는데 계속 답이 나오지 않았다. matrix를 출력해보니 한 방향으로 가지 않는 것이였다. 그래서 살펴보니 directions의 배열에 잘못 입력을 해서 문제였다. 배열을 잘 고쳐서 8방향 전부 갈 수 있게 만들어 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(-2, -1), (-1, -2), (2, 1), (1, 2), (-2,..
Graph 그래프는 정점(vertex)과 이들을 연결하는 간선(edge)으로 이루어진 데이터 구조를 말합니다. 그래프는 지도나 인터넷과 같은 물리적인 연결 관계를 나타내기 위해 사용되기도 하지만 그 외 다양한 추상적인 연관성을 나타내기 위해서도 사용됩니다. 이러한 그래프 중 간선에 방향성이 있는 그래프를 방향(direction)이 있다는 의미로 directed graph라 하며, 반대로 간선에 방향성이 없는 그래프를 undirected graph라 합니다. 그래프 탐색 방법에는 대표적으로 2가지가 있습니다. 깊이 우선 탐색인 DFS와 너비 우선 탐색인 DFS가 있습니다. 아래에는 2가지 방법에 대한 설명을 적었습니다. DFS (Depth First Search) - 깊이 우선 탐색 DFS 방법은 root..
