[BOJ - JAVA] 1952 - 달팽이 2 (시뮬레이션, DFS, 구현)

# 주소

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

1952번: 달팽이2

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Solution{
	static int n, m;
	static int[][] arr;
	static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		m = scan.nextInt();
		n = scan.nextInt();
		arr = new int[m][n];
		arr[0][0] = 1;
		int nx = 0, ny = 0;
		int answer = 0;
		int d = 0;
		int temp = 0;
		while(true) {
			 nx = nx + dir[d][0];
			 ny = ny + dir[d][1];
			 if(nx < 0 || ny < 0 || nx >= m || ny >= n || arr[nx][ny] == 1) {
				 nx = nx - dir[d][0];
				 ny = ny - dir[d][1];
				 d = (d + 1) % 4;
				 temp++;
			 }
			 if(temp == 4)
				 break;
			 else if(arr[nx][ny] == 0) {
				 if(temp > 0)
					 answer++;
				 temp = 0;
				 arr[nx][ny] = 1;
			 }
		}
		System.out.println(answer);
	}
}

이게 브론즈 1 문제라고 하네요. 

다들 보니까 쉽게쉽게 풀던데 저는 SWEA에서 이 문제를 처음 접했을 땐 변수를 정말 많이 두고 풀었었습니다.

그런데 백준 사이트에서 이 문제를 다시 접해보니 꼭 그러지 않아도 되겠다 싶어 원래 있었던 VISIT배열도 없애버리고 단순히 인덱스조절만으로 풀었습니다.

결정적으로 visit이 없어도 되는 이유는 arr값을 0과 1로 조절하여 재방문을 피할 수 있기 때문에 그런데요.

만약 arr를 안쓰겠다면 visit배열 하나만으로 풀 수도 있어야겠습니다.

 

이 문제에서 핵심은 인덱스를 주어진 범위의 밖으로 나가지 않게, 방문한 곳의 재방문은 피하는 것이 핵심입니다.

따라서 방문할 수 없는 곳에 맞닥뜨리면 방향을 바꾸어 주는데 이 떄 시계방향으로 바뀌므로 그 횟수가 총 4번이 될 때 break하여 정답을 출력해내는 원리로 푸시면 되겠습니다.

따라서 이 때 사용되는 temp  변수는 지역변수로 방문할 수 있는 곳을 방문할 때마다 0으로 초기화하는 작업이 반드시 필요하고 temp가 쌓여 있을 때에만 정답값인 answer를 증가시켜주는 것도 필요하겠습니다.

nx와 ny는 새로 갱신되는 arr의 인덱스인데 이것은 dir라는 방향 벡터를 통해 하나의 방향에 대해서만 계속 나아가며 방문할 수 없는 곳일 때에는 d값을 증가시켜야합니다.

 

방문하려했을 때 방문할 수 없는 곳이면 원래 위치로 돌아가는 것도 중요합니다.

따라서 nx와 ny에 대해 기존에 더했던 값들을 빼고 방향을 재설정하여 다시 더해주는 방식으로 풀어야 합니다.

d의 값은 방문할 수 없는 상황에 대해서만 증가할텐데 4를 넘어가면 안되므로 4로 나눈 나머지로 표현하여야합니다.

 

감사합니다.