💡문제
m × n 직사각 그리드(rectangular grid)는, x-좌표의 범위가 0부터 n-1까지인 정수이고 y-좌표의 범위가 0부터 m-1까지 정수인 평면상의 점들에 대응하는 정점들을 가지고, 두 정점에 대응하는 두 점 사이의 거리가 1 일 때에만 그 둘을 잇는 에지가 있는 그래프다. 예를 들어, 4 × 6 직사각 그리드가 그림 1 에 있다. 이 그리드는 m개 행 각각에 n개의 정점이 있고, n개 열 각각에 m 개의 정점이 있다. 행 i와 열 j에 있는 정점을 (i,j)라고 나타낸다. 여기서 0 ≤ i ≤ m-1이고 0 ≤ j ≤ n-1이다.
m × n 직사각 그리드의 모든 행 i ∈ {0, … , m-1}에 대하여 두 정점 (i, 0)과 (i, n-1)을 잇는 에지를 추가하고, 또한 모든 열 j ∈ {0, … , n-1} 에 대하여 두 정점 (0, j) 와 (m-1, j) 을 잇는 에지를 추가하면, 그림 2 에 보인 것과 같이 각 행은 길이 n인 사이클을 이루고 각 열은 길이 m인 사이클을 이루게 된다. 이렇게 만들어진 그래프를 종종 m × n 토로이드 그리드(toroidal grid) 라고 부르는데, 왜냐하면 이 그래프를 토러스(torus)에 에지가 교차하지 않도록 그릴 수 있기 때문이다.
주어진 m × n 토로이드 그리드에 대하여, 모든 정점을 정확히 한번씩 지나는 사이클을 찾는 프로그램을 작성하시오. 문제에서 요구하는 사이클은 그래프에 있는 서로 다른 mn개 정점들의 열 (v1, v2, … , vmn)로 나타낼 수 있는데, 이때 모든 k ∈ {1, … , mn-1}에 대하여 vk와 vk+1은 인접하며 또한 vmn과 v1도 인접하여야 한다.
입력
표준입력에서 데이터를 읽는다. 입력은 T개의 의 테스트 데이터로 구성되어 있다. 입력의 첫째 줄에 입력 데이터의 개수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 두 정수 m과 n을 포함하는 한 줄로 구성되어 있는데, 입력 그래프가 m × n 토로이드 그리드임을 가리킨다. 여기서 3 ≤ m, n ≤ 100이다.
출력
표준출력으로 데이터를 출력한다. 각 테스트 데이터에 대해, 출력의 첫째 줄에는 조건을 만족하는 해가 존재하는지 아닌지를 나타내는 정수를 출력해야 한다. 만약 해가 존재하면, 그 정수는 1 이어야 한다; 그렇지 않으면 -1 이다. 첫째 줄이 1 일 경우에만 추가로 문제에서 요구한 사이클의 정점 열(sequence)을 mn 개의 줄에 출력한다. 복수의 해가 가능하면, 그 중 임의의 하나를 출력하면 된다. 어떤 줄에도 공백 문자(빈칸이나 탭)는 허용되지 않는다.
예제입력
2
3 4
3 3예제출력
1
(0,0)
(0,1)
(1,1)
(1,2)
(0,2)
(0,3)
(1,3)
(2,3)
(2,2)
(2,1)
(2,0)
(1,0)
1
(2,2)
(2,0)
(1,0)
(0,0)
(0,1)
(0,2)
(1,2)
(1,1)
(2,1)📖내가 작성한 Code
import sys
'''
3<=m,n<=100
그냥 00 출발해서 1까지 와리가리 그다음 쭉 올라가기
'''
def find_line(m,n):
answer = [1,(0,0)]
for i in range(m):
if i%2:
for j in range(1,n):
answer.append((i,j))
else:
for j in range(n-1,0,-1):
answer.append((i,j))
for i in range(m-1,0,-1):
answer.append((i,0))
return answer
def main():
inputs = map(int,sys.stdin.read().split())
result = []
for _ in range(next(inputs)):
m,n = next(inputs),next(inputs)
result.extend(find_line(m,n))
print('\n'.join(map(str,result)))
if __name__ == '__main__':
main()
✍️풀이과정
처음에는 무슨 말인지 몰랐다. 이게 불가능할 수 가 있나? 라고 생각했기 때문이다. 그냥 어떤식으로 하던 전부 되는거 아닌가 생각했는데, 혹시나 해서 홀수,짝수 해봤는데도 똑같음. 그냥 구현 문제인가 싶어 넘어감. 알고리즘을 보니까 애드 혹.
푸는 사람도 없나봄.
🧠 코드 리뷰
-
경로 생성 방식 개선: 현재 코드는 지그재그 형태로 경로를 생성한 후, 첫 번째 열을 따라 역방향으로 이동하는 경로를 추가하고 있습니다. 그러나 이러한 방식은 불필요하게 복잡하며, 단순히 첫 번째 열을 따라 내려가고 마지막 행을 따라 오른쪽으로 이동하는 방식으로도 경로를 생성할 수 있습니다.
-
입력 처리 방식 개선: 현재 코드는 sys.stdin.read()를 사용하여 모든 입력을 한 번에 읽은 후, 이를 처리하고 있습니다. 그러나 이는 입력이 많을 경우 메모리 사용량이 증가할 수 있습니다. 대신, 표준 입력을 한 줄씩 읽어 처리하는 것이 더 효율적일 수 있습니다.
-
출력 형식 일관성 유지: 현재 코드는 좌표를 문자열로 변환하여 출력하고 있습니다. 그러나 좌표를 출력할 때 일관된 형식을 유지하는 것이 좋습니다. 예를 들어, 좌표를 (x, y) 형식으로 출력하려면 다음과 같이 수정할 수 있습니다.
🛠️AI 개선 코드
def find_line(m, n):
answer = [1, (0, 0)]
for i in range(1, m):
answer.append((i, 0))
for j in range(1, n):
answer.append((m - 1, j))
return answer
def main():
import sys
input = sys.stdin.read
data = input().split()
index = 0
t = int(data[index])
index += 1
result = []
for _ in range(t):
m = int(data[index])
n = int(data[index + 1])
index += 2
result.extend(find_line(m, n))
for coord in result:
if isinstance(coord, int):
print(coord)
else:
print(f"({coord[0]}, {coord[1]})")
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
