[BOJ] 1913. 달팽이 (Java)

문제 링크 / level: Silver V

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

1913번: 달팽이

 

 

내가 생각한 풀이

예전에 SWEA의 D2 레벨에서 비슷한 유형의 문제를 풀었던 적이 있다. 그래서 오래간만에 복습 좀 할겸 BOJ에 있는 문제를 하나 풀어봤는데 꽤 헤매서 당황스러웠다. 디버깅까지 해보는 초유의 사태 발생...😥

 

문제의 핵심 (출처: BOJ)

문제는 심플하다. 입력값으로 N이 주어지면 N^2 사이즈의 이차원 배열을 하나 만들고 그 안을 1부터 N^2까지의 수로 채워나가면 된다. 이때 채워나가는 방식이 뱅글뱅글 도는 모양이라서 달팽이라고 하는 것 같다. (그래서 내 코드의 배열 이름은 snail이다^_^)

 

아무튼 보기에는 쉬워보이는데 한 번도 짜본 적 없다면 처음에는 시간이 꽤나 걸리는 문제임.

참고로 SWEA에서는 D2 레벨에 이 문제가 있다. 조금 다르긴 하지만 참고용으로 링크를 걸어본다. [1954. 달팽이 숫자]

 

시작해보즈아~~~!

시작하기에 앞서 생각해야할 것들이 있다.

1. 뱅글뱅글 도는 방향의 순서

2. 숫자는 커지는가, 작아지는가?

3. 언제, 어디서 방향을 바꿔줄 것인가?

 

N=5일 때 (출처: BOJ)

N=4일 때 (출처: SWEA)

일단 BOJ의 문제에서는 N이 무조건 홀수로 주어진다고 한다. SWEA에서는 그런 조건은 없었음. 근데 어차피 N이 홀수든 짝수든 이 문제를 푸는데 영향이 있는지는 모르겠다.

 

 

1. 방향의 순서 & 2. 숫자는 커지는가, 작아지는가?

보면 알겠지만 내가 처음에 풀어봤던 SWEA문제는 배열의 (0,0) 위치에서 1로 시작하면서 ➡⬇⬅⬆ 방향으로 돈다. 그리고 1부터 16까지 차례대로 숫자가 들어간다.

한편, 이번에 푼 BOJ 문제는 1이 가장 안쪽에 있는 형태다. 그래서 처음에는 1이 있는 곳부터 돌아나오는 방법을 생각했는데 그렇게 풀면 방향전환을 위해 생각할 것이 너무 많아지는 형국이었다.. 이건 아닌 것 같아. 정신을 차리고 다시 보니 굳이 그렇게 풀 필요 없이 SWEA랑 똑같이 풀면 되는 문제로 보였다. SWEA 문제가 1부터 증가하는 형태였다면, BOJ 문제는 N^2부터 1씩 감소하는 형태인 것만 다르다는 것. 그거 외에는 다른 점이 없었다. 자신감이 생겼다.😎💪

그리고 N^2부터 시작해서 1로 가는 길의 방향을 살펴보면 ⬇➡⬆⬅이다. 전문용어로는 시계반대방향이라고 할 수 있겠다^_^

 

결론: 배열의 (0,0) 위치에서 N^2로 시작해서 시계반대방향으로 돌며 1씩 감소한다.

 

 

3. 언제, 어디서 방향을 바꿔줄 것인가?

1번과 2번의 답을 찾았다면 실제 코드를 구현할 때는 이게 포인트겠다.

(1) 배열의 범위를 벗어나거나 (2) 배열의 원소가 0이 아니라면 방향을 바꿔줘야 한다.

 

참고로 배열은 처음에 모든 원소가 0으로 초기화되어있는 상태다. (*나는 static으로 선언)

방향을 전환할 필요가 없을 때는 원소의 값을 업데이트 해주기 때문에 0으로 남아있는 애들만 업데이트 해주면 된다. 이미 업데이트한 애들은 건드리면 안되기 때문에 0이 아닌 애들을 만났을 때는 방향을 전환해줘야하는 것임.

 

이건... 말로 구구절절 하는 것보다는 직접 한 번 코드로 짜보는게 빠를 거라고 생각한다.😊

---

예전에 한 번 짜봤던 코드에서 달팽이의 회전 방향과 숫자가 증가하는 것이 아니라 감소하는 것이라는 두 가지 조건만 바뀐거라서 사실 가볍게 5분컷 할 줄 알았는데 웬 뜬금없는 Array의 인덱스 범위를 벗어났다는 오류가 떠서 고생 좀 하다가 결국 디버깅을 통해 문제를 해결했다.😔 (feat.옆에서 디버깅도 실력이라고 구박하는 짝꿍과 함께 ㅎㅎ)

// 핵심 코드
for (int i = 0; i < len; i++) {
	for (int j = 0; j < len; j++) {
		snail[y][x] = N--;
		if (y + dy[d] < 0 || x + dx[d] < 0 || y + dy[d] >= len || x + dx[d] >= len
				|| snail[y + dy[d]][x + dx[d]] != 0) {
			d++;
			if (d == 4) d = 0;
		}
		y += dy[d];
		x += dx[d];
	}
}

나는 처음에 변수 하나 덜 쓰겠다고 N *= N 으로 해놓고 for문을 돌렸고 (처음엔 len 대신 snail.length를 썼었음. 어차피 무조건 정사각형이니까^_^) 코드를 다 작성한 후에 실행시켜보니 if문 안에서 배열 범위를 벗어났다는 오류가 계속 떴다.

 

근데 내 코드 상에서 if문 안을 || (OR)로 연결했기 때문에 하나라도 true가 나오면 뒤까지 보지 않고 그냥 전체를 true로 생각하고 넘겨버리기 때문에 만약 배열 범위를 벗어나는 경우 snail[y + dy[d]][x + dx[d]]까지 갈 일이 없어서 배열 범위를 벗어났다는 에러를 만날 일이 절!! 대!! 로!! 없단 말이지???🤔 근데 왜 이러능교???

 

짝꿍의 조언(?)을 따라 디버깅을 해본 결과......

처음에 짰던 코드는 for문 조건에서는 N *= N인 것을 인지하고 snail.length와 같이 입력해서 문제가 없었으나, if문 안에서 조건을 작성할 때는 이를 잊어버리고 y + dy[d] >= N라는 코드를 작성해버린 것이다. for문을 돌 때마다 그 위에 있는 N-- 때문에 값이 하나씩 줄어드니 뭔가 문제가 생긴 것이 분명했다.

 

문제를 발견한 나는 더이상 깝치지 않기로 하고 len이라는 변수를 하나 만들어서 N 값을 저장해두고 안전하게 사용했고, 이후 해피엔딩으로 끝났다는 이야기🤗🌸

 

예전에도 이거 때문에 고생한 적 있었는데 또 당했다. 앞으로는 까불지 말자🤦‍♀️