[백준 1952번] 달팽이2

문제

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

ㅇ

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

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

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

입력

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

출력

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

예제 입력 1 복사

5 3

예제 출력 1 복사

5

 

메모

import java.util.Scanner;

public class Main {

	//map setting
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);

		M = sc.nextInt();
		N = sc.nextInt();
		sc.close();
		
		map = new int[M][N];
		visited = new boolean[M][N];
		
		//current position
		int x=0, y=0;	
		int total = M*N;
		
		//direction
		int[] dx = {0,1,0,-1}; //right, down, left, up 
		int[] dy = {1,0,-1,0}; 
		
		visited[x][y] = true;   //시작점 표시 
		int direction = 0; 		//현재 방향
		int directionCnt = 0;
		
		//움직인 횟수
		int cnt = 1;
		int xx=0, yy=0;
		//모든 구간 search 시 종료
		while(total > cnt) {
			
			//이동
			xx = x + dx[direction];
			yy = y+ dy[direction];
			
			//범위를 벗어나지 않고, 방문하지 않았으면 
			if( xx >=0 && yy >=0 &&   M > xx && N > yy && !visited[xx][yy] ) {
				
				x = xx;
				y = yy;
				
				visited[x][y] = true;
				cnt++;
			}else {
				
				direction++;	//방향 전환 
				directionCnt++; //꺽인 횟수 입력
				
				if(direction > 3) {
					direction %= 4; 
				}
			}
		}
		
		System.out.println(directionCnt);
	}
	
	
}