[BOJ] 1952. 달팽이2
https://www.acmicpc.net/problem/1952
문제
M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.
위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.
위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?
입력
첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 100)
출력
첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.
예제 입력
5 3
예제 출력
5
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} | |
} |
👩💻 풀이과정
- 오른쪽, 아래, 위, 왼쪽 순서로 탐색
- 이미 탐색한 위치는
isVisited
방문 처리 - 현재 탐색하는 방향으로 탐색
- 탐색한 위치가 범위 안이거나, 아직 방문하지 않은 곳이라면
- 지나온 칸 수 +1
sum + 1
- 탐색한 위치 방문 처리
isVisited=true
- 지나온 칸 수 +1
- 탐색한 위치가 범위 밖이거나, 이미 방문한 곳이라면
- 다음 탐색할 방향으로 방향 전환
idx + 1
- 방향 전환
cnt + 1
- 다음 탐색할 방향으로 방향 전환
- 방향 전환할 때
idx
가 4 이상이면 다시 0으로
- 탐색한 위치가 범위 안이거나, 아직 방문하지 않은 곳이라면
- 모든 칸 탐색하면 종료
sum == N x M