[BOJ] 10252번 그리드 그래프

[BOJ] 10252번 그리드 그래프 문제

굉장히 재밌었던 문제다. 먼저, 이 글을 읽는 사람은 반드시 이 문제를 풀다가 막혔거나, 이미 푼 사람이 봤으면 좋겠다.

---

이 문제는 아주 간단하게 요약하면, 기존 그래프와 달리 위아래, 좌우가 연결되어 있는 토로이드 그래프에서 한 붓 그리기가 가능한지와 있다면 그 경로를 아무거나 출력하는 것이다.

아무거나라는 말에서 알 수 있듯, 이는 구성적(Constructive) + 애드 혹(Ad hoc)의 문제다. 즉, 푸는 방법의 정해는 딱히 없고, 본인이 해결한 그 방법이 정답이 되는 환경의 문제인 셈이다. 그렇기 때문에 서두에 이 문제를 풀다가 막힌 사람이 봤으면 하는 말을 쓴 것이다.

즉, 앞으로 작성될 문제의 정답은 나의 정답이며, 이 외에도 정말 많은 답이 있다는 것을 알아주길 바란다.

아마도 이 글들의 정답은 다 다를 것이다

---

앞서 말한 문제의 핵심으로 다시 가서, 이 문제는 토로이드 그래프라는 성질을 최대한 잘 사용하면 된다. 즉, 처음으로 돌아가려면 모든 정점을 지나 마지막엔 처음으로 시작하는 정점과 같은 행 또는 열의 옆에만 있으면 된다.

다만 행과 열의 개수가 홀짝인 것에 따라 풀이가 달라지기에 나는 이를 최대한 무시하는 방향으로 문제를 풀었다. 이유는 단순히 귀찮아서... 다.

내가 생각한 답은 바로 끝 열을 제외한 나머지 열들에서 ㄹ자 형태로 돌아주고, 마지막 열을 행의 역순으로 적는 형태였다. 이 방법은 행의 개수가 홀짝에 관계없이, 열의 개수에 상관없이 무조건 성립하는 방법이다.

백문이불여일견

개인적으로 토러스의 성질을 최대한 써먹음과 동시에 구현하기 쉬운 방법이라고 생각한다.

import sys

if __name__ == '__main__':
    for T in range(int(sys.stdin.readline().rstrip())):
        m, n = map(int, sys.stdin.readline().rstrip().split())
        print(1)
        for i in range(m):
            if i&1:
                for j in range(n-2, -1, -1):
                    print(f'({i},{j})')
            else:
                for j in range(n-1):
                    print(f'({i},{j})')

        for i in range(m-1, -1, -1):
            print(f'({i},{n-1})')