러닝머신 하는 K-공대생

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 같은 색으로 이루어진 사이클을 찾는 과정은 간단하다. 같은 색으로 이루어진 공간만을 이동하면서 탐색을 진행하는데 만약 이동하려는 공간이 바로 전 depth에서 탐색한 노드가 아니고(다시 돌아가는 경우) 이전에 방문했었더라면 사이클을 만들 수 있다. 아래 코드에서 recur[]은 탐색하고자 하는 색에서 방문할 때마다 현재의 탐색깊이를 저장한 것이며 recur를 통해 이전에 방문했는지, 바로 이전에 탐색한 곳인지를 확인하고 모든 칸에서 DFS를 진행하는 방식..

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS로만 풀려고 하니 시간초과가 떠서 고민하다 DFS에서 탐색을 진행할 때 사이클을 이루는 경우를 제외하고 이전에 탐색한 것과 동일한 탐색을 반복하는 경우가 있다. 예를 들어 아래와 같은 맵이 있다고 하자. 이때 (0,0) 부터 시작해서 이동가능한 경로를 따라 dfs를 진행한다고하면 아래와 같이 트리를 따라 탐색을 진행한다. 이때 왼쪽에서 오른쪽으로 dfs가 진행되고 있다고 하면 왼쪽에서 dfs를 시행할 때 (1,3)에서 탐색한 것, (3,1)에서 탐색한 것,..

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 만약 연결 그래프라면 노드 1에서 부터 탐색을 시작해서 총 2가지 색을 이용해 인접 노드를 자신과 다른 색으로 색칠한다. 이때 이분 그래프를 만들때는 색깔을 기준으로 노드를 분류하면 된다. 만약 어떤 노드의 색과 그 노드의 인접 노드의 색이 같은 것이 있다면 이분 그래프는 불가능하다. 연결 그래프가 아니라면 색칠된 수와 전체 노드의 수를 비교했을 때 이 둘이 다를 경우이다. 따라서 이때는 노드 1에서 시작하지 말고 다른 노드들에서 시작해서 동일한 색..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제의 조건에 맞는 A,B,C,D,E 가 존재한다는 것은 각 사람들을 노드로 두고, 친구관계를 갖는 두 사람을 연결하는 간선으로 그래프를 생각하면, 어떤 한 노드에서 시작해서 다른 노드로 이동할때 탐색 깊이가 4 이상이라는 것이다. 즉 DFS를 이용해 어느 한 노드에서부터 시작해 다른 노드를 탐색할 때 깊이가 4 이면 조건을 만족한다고 볼 수 있다. 따라서 처음에 아래와 같이 DFS 코드를 작성했다. def dfs(v,graph,visited,depth): visited[v] = True # 만약 탐색 깊이가 4이면 가능 if depth == 4: print(1) ex..