[SSAFY][D2]swea_1954 달팽이 숫자

문제

유명한 문제이다.
사실 처음 보면 이거 어떻게 접근해야 할지 어려워 하는 분들이 많을 것 같은데, 어렴풋이 2학년때 배웠던 객지프에서 풀었던 생각이 나서 그 아이디어로 푼 것 같다.

dfs를 이용한 문제라고 하는데, 난 걍 아이디어 생각나는대로 푼거라, 풀이 정리하고 dfs 이용한 풀이 + dfs 개념도 한 번 정리해보려고 한다.

접근 방법

이 문제의 경우, 일반적인 배열과는 달리 달팽이 모양처럼 오른쪽 -> 아래 -> 왼쪽 -> 위쪽의 순서가 이어진다는 것이 특징이다.

예시의 3*3 배열을 예시로 그림을 그려보면 다음과 같다.

즉, 이 배열을 구현하기 위해서는 "방향"을 나타내는 변수를 둬야하고, 그 변수에 따라서 이중배열의 i,j를 다르게 조정해서 숫자를 써내려가야한다

즉, 다음과 같은 결론에 도달한다.

1. 각 사방향을 나타내는 변수가 있고, 그 변수에 따라서 i,j 값을 다르게 해서 숫자를 쓴다.
2. count 값을 둬서 숫자를 써내려간다.
3. 배열의 경우, 이미 채워져 있는건 건들면 안 된다. 즉 같은 크기를 가진 boolean 배열을 둬서 비교하면서 써내려간다.
4. list이므로 index를 넘지 않는 것이 중요하다. 즉, 조건 검사를 할때 index 검사를 맨 앞단에 둬서, 인덱스 숫자가 넘치면 [ ][ ] 비교까지 가지 않도록 한다.

풀이

import java.util.ArrayList;
import java.util.Scanner;

public class swea_1954 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		StringBuilder stb = new StringBuilder();
		
		for(int k = 1; k<=n; k++) {
			int num = sc.nextInt();
			
			int count = 1;
			int i = 0;
			int j = 0;
			
			boolean right = true;
			boolean left = false;
			boolean up = false;
			boolean down = false;
			
			int[][] snail = new int[num][num];
			boolean[][] ox = new boolean[num][num];
			
			while(count <= num*num) {
				if(right) { //j++
					while(j < num && ox[i][j] == false ) {
						snail[i][j] = count;
						ox[i][j] = true;
						count++;
						j++;
					}
					j--;
					i++;
					
					right = false;
					down = true;
				}
				
				if(down) { //i++
					while(i < num && ox[i][j] == false) {
						snail[i][j] = count;
						ox[i][j] = true;
						count++;
						i++;
					}
					i--;
					j--;
					
					down = false;
					left = true;
				}
				
				if(left) { //j--
					while(j >= 0 && ox[i][j] == false) {
						snail[i][j] = count;
						ox[i][j] = true;
						count++;
						j--;
					}
					j++; //-1이 되어 버리므로
					i--;
					
					left = false;
					up = true;
				}
				
				if(up) { //i--
					while(i >= 0 && ox[i][j] == false) {
						snail[i][j] = count;
						ox[i][j] = true;
						count++;
						i--;
					}
					i++; //-1이 되어 버리므로
					j++;
					
					up = false;
					right = true;
				}
			}
			
			stb.append("#" + k);
			stb.append("\n"); //줄바꿈
			for(int z = 0; z<num; z++) {
				for(int t = 0; t<num; t++) {
					stb.append(snail[z][t] + " ");
				}
				stb.append("\n"); //줄바꿈
			}
		}
		System.out.println(stb);
	}
}

그리고 이 문제의 경우, 출력 방식이 다음과 같이 되어 있다.

즉, case 마다 출력하는 것이 아니라 한번에 모아서 출력하는 방식을 써야한다.(이렇게 안하면 fail 나온다...사실 문제도 문젠데 이 부분때매 많이 헤맸다ㅠ) 그래서 나의 경우는 StringBuilder를 이용해서 저장한다음, 한번에 출력하는 방식을 사용했다.

StringBuilder에 대한 설명은 다음을 참고 바란다.

결과