Bull

https://www.acmicpc.net/problem/1987문제좌표의 크기가 주어지고, (1,1)부터 시작하는데 같은 알파벳을 만나면 안될때 까지 상하좌우로 움직일 시 최대한 많이 갈 수 있는 칸은 몇인지 찾는 문제이다.아이디어DFS와 백트래킹을 이용한다.인접한 상하좌우 좌표를 확인하여 기록된 알파벳이 없으면 DFS를 호출한다. 여기서 백트래킹을 추가하여 DFS를 통해 visited(알파벳)을 기록하는데 갈수 있는 곳 까지 간 후 다시 visited를 해제하는 방식을 이용한다.위 GIF는 문제의 예제로 백트래킹과 DFS가 어떻게 동작하는 지 그림판으로 나타내보았다. H-A에서H-A-D-G-J-FH-A-J-G-DH-A-J-F-D의 DFS가 적용되고 H-F에서H-F-J-A-D-GH-F-J-G-D-AH-..

https://www.acmicpc.net/problem/1707 문제이분 그래프란?그래프 이론에서 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 쉽게 말해서 어느 정점을 선택했을 때 간선을 통해 어디로 가든 RBRBRB...로 반복되어야 한다. (RED, BLUE) 이것을 풀어서 생각하면 두 집합으로 나눌 수 있는 그래프를 말한다. 즉 왼쪽이 있는 그래프를 모양만 좀 다르게 위치를 옮겨주면 오른쪽 그림이나 사실 똑같은 건데, 이런식으로 오른쪽 그림으로 만든 후 선 그어서 두 집합으로 나뉘어지면 그게 이분 그래프다. 아이디어BFS, DFS 방식으로 모두 풀이가 가능하다. ..