(백준 / BOJ)(Python) 27513 – 뱀 그리기

(백준 / BOJ)(Python) 27513 – 뱀 그리기

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

27513호: 뱀 그리기

한 줄에 공백으로 구분된 두 개의 정수 $n$ 및 $m$. ($2 \le n,m \le 200$) $n$은 $x$ 축의 길이이고 $m$은 $y$ 축의 길이입니다.

www.acmicpc.net

문제를 풀다

셀 수를 계산하는 과정은 https://dodobow./24를 참조하십시오. 너비와 높이가 모두 홀수인지 아닌지에 따라 N * M – 1과 N * M의 정답을 얻는 방법을 알아보겠습니다.

구현하기가 매우 번거롭고 혼란스럽습니다.


너비와 높이가 모두 홀수인 경우

위 그림은 N=5, M=5인 경우입니다.

너비와 높이가 모두 홀수인 경우 위 그림처럼 움직이면 (1, 1)에서 시작해서 (2, 1)로 가고, 머리와 꼬리가 인접해 있는 경우인데 한 칸만 빼고 나머지는 채울 수 있다.


너비와 높이 중 적어도 하나가 짝수인 경우

너비나 높이가 짝수이면 위의 그림과 같이 짝수 길이 방향으로 곧게 걷다가 (1, 1)에서 시작하여 (2, 1)까지 S자 모양을 위로 그리면, 머리와 꼬리가 인접한 경우이며 모든 셀을 채울 수 있습니다.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
if n % 2 and m % 2: #가로와 세로 모두 홀수라면
    print(n * m - 1) #칸 수 출력
    #경로 출력
    x, y = 1, 0
    for i in range(m):
        y += 1
        print(x, y)
    for i in range(m - 2):
        if i:
            y -= 1
        if i % 2:
            for j in range(n - 1):
                print(x, y)
                x -= 1
        else:
            for j in range(n - 1):
                x += 1
                print(x, y)
    for i in range(n - 1):
        if i % 2:
            if x == 2:
                print(2, 1)
                break
            else:
                print(x, 1)
                print(x, 2)
        else:
            print(x, 2)
            print(x, 1)
        x -= 1
else: #가로와 세로 중 하나라도 짝수라면
    print(n * m) #칸 수 출력
    #경로 출력
    if m % 2:
        x, y = 0, 1
        for i in range(n):
            x += 1
            print(x, y)
        for i in range(n):
            if i:
                x -= 1
            if i % 2:
                for j in range(m - 1):
                    print(x, y)
                    y -= 1
            else:
                for j in range(m - 1):
                    y += 1
                    print(x, y)
    else:
        x, y = 1, 0
        for i in range(m):
            y += 1
            print(x, y)
        for i in range(m):
            if i:
                y -= 1
            if i % 2:
                for j in range(n - 1):
                    print(x, y)
                    x -= 1
            else:
                for j in range(n - 1):
                    x += 1
                    print(x, y)