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


문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.
스크린샷 2023-05-15 오후 5 42 44

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

스크린샷 2023-05-15 오후 5 43 24

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


입력

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


출력

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


예제 입력

5 3


예제 출력

5


코드

import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] map;
static int[] dx = {0, 1, 0, -1}; // 오른쪽으로, 아랫쪽으로, 왼쪽으로, 윗쪽으로
static int[] dy = {1, 0, -1, 0};
static boolean[][] isVisited; // 방문 처리
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
sc.close();
map = new int[M][N];
isVisited = new boolean[M][N];
int cnt = 0; // 출력할 꺽은 횟수
int sum = 0; // 지나온 칸 수 -> 종료 조건으로 사용
int idx = 0; // 다음 칸 탐색할 때 쓸 인덱스
int nowX = 0; // 현재 좌표
int nowY = 0;
isVisited[nowX][nowY] = true;
sum = 1;
while(idx < 4) {
int nx = nowX + dx[idx]; // 탐색한 새로운 좌표
int ny = nowY + dy[idx];
// 모든 칸을 지나왔다면 답 출력하고 종료
if(sum == N*M) {
System.out.println(cnt);
return;
}
// 새로 탐색한 좌표가 범위 안에 있고 아직 방문하지 않은 곳이라면
if(nx >= 0 && ny >= 0 && nx < M && ny < N && !isVisited[nx][ny]) {
sum++; // 지나온 칸 수 + 1
isVisited[nx][ny] = true; // 방문 처리
nowX = nx; // 다음 탐색을 위해 갱신
nowY = ny;
}
// 이전 방향으로 탐색했는데 범위를 벗어났거나 이미 방문한 곳이라면
else {
idx++; // 다음 탐색할 방향으로 전환
cnt++; // 방향을 꺾었으므로 + 1
}
// 마지막 방향 인덱스까지 왔으면 다시 맨 처음 탐색 방향으로 전환
if(idx >= 4) {
idx = 0;
}
}
}
}
view raw 1952.java hosted with ❤ by GitHub


👩‍💻 풀이과정

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