[백준][Python] 1952. 달팽이 2

Bronze Ⅰ 🔗1952. 달팽이 2

📝문제 요약

문제 설명

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

ㅇ

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

ㅇ	→	↘
↗	↘	↓
↑	↓	↓
↑	끝	↓
↖	←	↙

위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 100)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.

✏️문제 풀이

• m, n을 입력 받음
• m*n 이차원 배열 생성하고 0으로 초기화
• dx, dy : 오른쪽 → 아래 → 왼쪽 → 위
• 방향 꺾은 횟수(cnt): 마지막 꺾임은 직선이 아니므로 -1 사용, 현재 위치(x, y), 현재 방향 인덱스(direction) 초기화
• m*n 번 반복하여 모든 위치를 확인
  • 현재 위치 x, y에 i+1을 채움
  • 다음 위치가 배열 범위를 벗어나거나, 이미 숫자가 채워져 있으면 방향을 꺾음
    • cnt += 1 : 꺾은 횟수 카운팅
    • 방향을 바꾸고 다시 nx, ny 갱신
  • 다음 위치로 이동
• 총 직선 횟수 출력

코드와 함께 보는 풀이

# m, n을 입력 받음
m, n = map(int, input().split())
# m*n 이차원 배열 생성하고 0으로 초기화
table = [[0] * n for _ in range(m)]

# 이동을 위한 dx, dy : 오른쪽 → 아래 → 왼쪽 → 위
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

# 방향 꺾은 횟수 초기화 : 마지막 꺾임은 직선이 아니므로 -1 사용
cnt = -1
# 현재 위치(x, y) 초기화
x, y = 0, 0
# 0 : 오른쪽, 1 : 아래, 2 : 왼쪽, 3 : 위
direction = 0

# m*n 번 반복하여 모든 위치를 확인
for i in range(m*n):
		# 현재 위치 x, y에 i+1을 채움
    table[x][y] = i+1
		
		# 다음 위치 계산
    nx = x + dx[direction]
    ny = y + dy[direction]
		
		# 다음 위치가 배열 범위를 벗어나거나, 이미 숫자가 채워져 있으면 방향을 꺾음
    if (nx < 0 or nx >= m or ny < 0 or ny >= n or table[nx][ny] != 0):
        # 다음 direction을 사용 : 밯향을 꺾음
        direction = (direction + 1) % 4
        # 꺾은 횟수 카운팅
        cnt += 1
        # 방향을 바꾸고 다시 nx, ny 갱신
        nx = x + dx[direction]
        ny = y + dy[direction]
		
		# 다음 위치로 이동
    x, y = nx, ny

# 총 직선 횟수 출력
print(cnt)

💯제출 코드

m, n = map(int, input().split())
table = [[0] * n for _ in range(m)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

cnt = -1
x, y = 0, 0
direction = 0

for i in range(m*n):
    table[x][y] = i+1

    nx = x + dx[direction]
    ny = y + dy[direction]

    if (nx < 0 or nx >= m or ny < 0 or ny >= n or table[nx][ny] != 0):
        direction = (direction + 1) % 4
        cnt += 1
        nx = x + dx[direction]
        ny = y + dy[direction]

    x, y = nx, ny
  
print(cnt)