후라이

https://www.acmicpc.net/problem/2206 입력첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.출력첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다. 해당 백준 문제는 BFS를 심화한 문제로, NxM의 숫자 맵에 1이 존재할 경우(벽이 존재할 경우), 이 벽을 허물 수 있다는 경우의 수까지 포함하여 최단 거리를 구하는 문제이다. 단, 벽은 한번만 허물 수 있다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.  우선, 기존의 BFS 최단거리 문제 틀에서 ..

https://www.acmicpc.net/problem/1707  해당 백준 문제는 이분 그래프 판별 문제이다.BFS, DFS 문제를 꾸준히 풀었다면 쉽게 풀이할 수 있을 것이다. 이분 그래프란?: 그래프의 정점들을 두 개의 집합으로 나누었을 때, 각 집합에 속한 정점끼리는 서로 간선으로 연결되지 않으며두 집합에 속한 정점들끼리만 간선으로 연결된다는 것. (1) 정점 집합 분할 : 이분 그래프는 정점들을 두 개의 집합으로 나눌 수 있다.즉, 집합 A와 집합 B가 있고, 각 간선은 집합 A의 정점과 집합 B의 정점 간에만 존재한다. (2) 인접 정점  : 두 집합에 속한 정점들은 서로 인접해야 하며, 같은 집합에 속한 정점들끼리는 인접하지 않다.   이분 그래프인지 아닌지를 탐색하는 데에는 BFS, DF..