[백준] 10252번 : 그리드 그래프 - JAVA[자바]

https://www.acmicpc.net/problem/10252

10252번: 그리드 그래프

 

---

■ 문제

 

 

---

■ 문제 이해

예제를 보면 그림1의 4 x 6 직사각 그리드가 있다.

해당 그리드를 두 번째 문단의 설명을 따라 이러쿵저러쿵 만져주면 그림2와 같은 형태로 에지가 연결된 그리드가 완성된다.

그렇게 완성된 그림2의 그리드에서 모든 정점을 정확히 한 번씩 지나는 사이클을 찾으면 된다!

 

※주의 사항

1. 연결된 에지 간 이동을 할 수 있는 점을 유의하자.

2. "사이클"을 찾아야 하므로 시작과 끝이 연결되어 있어야 한다.

 

자! 문제 이해는 끝났으니 어떻게 풀 수 있는지 알아보자!

 

---

■ 풀이

입력의 경우가 네 가지 형태로 나올 수 있다고 생각하고 풀었다.

 

1. 행, 열 모두 짝수일 경우

2. 행, 열 모두 홀수일 경우

3. 행은 홀수, 열은 짝수일 경우

4. 행은 짝수, 행은 홀수일 경우

 

네 가지 형태에서 모든 정점을 지나며 사이클을 형성할 수 있는 그림을 그려보았다.

사실상 열이 늘어나는 건 의미가 없기 때문에 행이 짝수인지 홀수인지만 보면 된다.

굳이 위에 그림처럼 사이클을 형성할 필요는 없지만, 내가 생각하기에 어떠한 형태의 그리드가 나와도 그림과 유사한 사이클로 해결할 수 있기에 이렇게 풀었다. (아래 두 그림이 이해되지 않는다면, 위에 주의 사항 1번을 보자)

 

탐색하기 위한 단계는 다음과 같으며, 그림을 보며 이해하자.

1. 1부터 시작하여 ㄹ자 형태로 탐색한다.

    - 그림과 같이 더 이상 나아갈 곳이 없다면 2로 이동한다. (에지 간 이동을 할 수 있음)

2. 2번부터 나머지를 탐색한다.

 

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());

            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());

            sb.append(printGridGraphPath(m, n));
        }

        System.out.println(sb);
    }

    public static String printGridGraphPath(int m, int n) {
        StringBuilder sb = new StringBuilder();

        // 실패하는 경우는 없다.
        sb.append("1").append("\n");

        // 왼쪽, 오른쪽 한 번씩 이동하기 위해 flag 선언
        boolean flag = false;

        for (int i = 0; i < m; i++) {
            // 왼쪽에서 오른쪽으로 이동
            if (!flag) {
                for (int c = 1; c < n; c++) {
                    sb.append("(").append(i).append(",").append(c).append(")").append("\n");
                }
            } else {
                // 오른쪽에서 왼쪽으로 이동
                for (int c = n - 1; c >= 1; c--) {
                    sb.append("(").append(i).append(",").append(c).append(")").append("\n");
                }
            }

            // 방향 전환을 위해 flag 반전
            flag = !flag;
        }

        // m - 1, 0 부터 0, 0까지 탐색
        for (int i = m - 1; i >= 0; i--) {
            sb.append("(").append(i).append(",").append(0).append(")").append("\n");
        }

        return sb.toString();
    }
}