[BOJ] 1952. 달팽이2

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

문제

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

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

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

입력

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

출력

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

예제 입력

5 3

예제 출력

5

코드

👩‍💻 풀이과정

• 오른쪽, 아래, 위, 왼쪽 순서로 탐색
• 이미 탐색한 위치는 isVisited 방문 처리
• 현재 탐색하는 방향으로 탐색
  • 탐색한 위치가 범위 안이거나, 아직 방문하지 않은 곳이라면
    • 지나온 칸 수 +1 sum + 1
    • 탐색한 위치 방문 처리 isVisited=true
  • 탐색한 위치가 범위 밖이거나, 이미 방문한 곳이라면
    • 다음 탐색할 방향으로 방향 전환 idx + 1
    • 방향 전환 cnt + 1
  • 방향 전환할 때 idx가 4 이상이면 다시 0으로
• 모든 칸 탐색하면 종료 sum == N x M