2001년 가을학기 문제해결기법 - 문제 1

그리드 그래프

행의 수가 [eqn: m]이고 열의 수가 [eqn: n]인 그리드 그래프(grid graph), 즉 [eqn: m times n] 그리드 그래프는 다음과 같이 정의되는 무향 그래프(undirected graph)이다: 정점의 집합 [eqn: V = \{ v_j^i \ | \ 1 le i le m, 1 le j le n \}]이고 에지 집합 [eqn: E = \{ (v_j^i , v_j'^i' ) \ | \][eqn: i'=i]이고 [eqn: j'=j+1]이거나 혹은 [eqn: j'=j]이고 [eqn: i'=i+1]이다[eqn: \}]. 아래 그림 1에 그리드 그래프의 예가 있다.

(a) [eqn: 3 times 3] 그리드 그래프

(b) [eqn: 3 times 4] 그리드 그래프

그림 1  그리드 그래프의 예

그리드 그래프는 위의 그림과 같이 정점에 색칠을 하는데, 두 가지 색으로 서로 인접한 정점에는 서로 다른 색이 되도록 색칠할 수 있다. 이런 성질을 가진 그래프을 이분 그래프(bipartite graph)라고 한다.

문제는 그리드 그래프가 입력될 때, 이 그래프가 가지고 있는 가장 길이가 긴 사이클(cycle)을 찾는 것이다. [eqn: 3 times 3] 그리드 그래프의 최장 사이클의 길이는 8이고, [eqn: 3 times 4] 그리드 그래프의 최장 사이클의 길이는 12가 된다.

프로그램명은 grid.c(grid.cpp)라고 하고 실행 파일명은 grid.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에는 그리드 그래프의 행의 수 [eqn: m]과  열의 수 [eqn: n]이 입력된다. [eqn: m]과 [eqn: n]은 2 이상이고 100이하인 양의 정수이다. 숫자 사이에 공백이 하나 혹은 그 이상 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 입력된 그리드 그래프의 최장 사이클의 길이를 첫째 줄에 출력한다. 둘째 줄부터 마지막 줄까지 한 줄에 한 정점씩 사이클을 출력한다. 사이클은 정점의 열로 나타낸다. 정점 [eqn: v_j^i]를 출력할 때 두 정수 [eqn: i]와 [eqn: j]를 공백을 하나 포함하여 출력한다. 답이 하나 이상일 수 있는데, 하나만 출력하면 된다. 시작 정점을 중복해서 출력하지 않는다.

입력과 출력의 예

INPUT.TXT

3 3

OUTPUT.TXT

8

1 1

1 2

2 2

2 3

3 3

3 2

3 1

2 1