[백준] 1913번 - "달팽이" (Java)

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

1913번: 달팽이

[백준] 1913 - 달팽이

---

 

난이도 : 실버 5

 

 코딩 테스트나 다른 구현 문제에서 한 번쯤 마주쳤을 법한 유형의 구현 문제입니다. 

 

 저는 주어진 문제 조건에 반대로 생각하여 문제를 해결하였습니다. 

 

 달팽이가 아래 그림과 같이 움직이는 것이 문제에서 주어진 조건입니다.

배열의 정가운데 요소부터 배열의 값을 채울 수 있고, 구현할 수 있지만 난이도가 높아지는듯한 느낌이 받았습니다.

(마우스로 그려서 좀 삐뚤빼뚤할 수 있습니다.)

조건에 따른 달팽이 움직임

반대로 생각하여, 달팽이의 움직임을 아래 그림과 같이 거꾸로 구현하였습니다. 

조건과 반대의 달팽이 움직임

 

1. 주어진 달팽이 움직임과 거꾸로 배열 요소를 삽입한다. (0,0)부터 시작.

2. direction(d)이 바뀌는 기준을 잡아준다. (범위를 벗어났거나, 이후 요소의 값이 존재하거나)

3. direction의 따라 다음 좌표의 값을 정한다. (d가 바뀔 경우, 바뀌지 않을 경우)

4. 값이 채워진 배열을 탐색 및 출력하면서 k의 위치를 찾는다. 

 

- static int [] dr = {1, 0, -1, 0}; 

- static int[] dc = {0, 1, 0, -1};

배열을 탐색할 방향을 설정해줍니다. (0,0)을 기준으로 달팽이 움직임의 역방향으로 탐색해야 하기 때문에 

하 -> 우 -> 상 -> 좌 순으로 좌표를 설정하였습니다. Java에서는 배열의 아래 방향이 +1이기 때문에 위와 같이 설정하였습니다.

 

- static int map [][]; 

 전역 변수로 사용할 map 변수입니다. 

 

- void main()

입력 및 전역 변수를 초기화합니다. makeMap() 함수를 호출하며 StringBuilder()를 사용하여 답을 출력합니다.

StringBuilder() 사용하지 않으면 시간 초과 오류가 뜹니다. 

 

- void makeMap(int n)

 주어진 n을 인자로 받으며, 달팽이의 움직임을 역으로 활용하여 배열의 요소를 삽입하는 함수입니다. 

변수 r, c를 이용하여 좌표를 만들고 count는 배열의 들어갈 값입니다. d는 방향입니다. 

 

 여기서 중요한 것은 d(방향)가 바뀌는 순간을 인지하는 것입니다. 

배열의 범위를 넘어가거나, 다음에 위치할 좌표에 이미 값이 있으면 방향(d)을 다음 방향으로 바꿔줍니다. 

방향에 따라서 다음 좌표가 결정되고, 방향은 setDirection() 함수를 통해 결정됩니다. 

 

- int setDirection (int d, int n, int nr, int nc)

 다음 좌표가 수행해야 할 방향을 결정하는 함수입니다. 

다음 좌표가 배열의 범위를 벗어났거나, 이미 값이 들어가 있으면 다음 방향으로 방향을 설정하여줍니다. 

 

  코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1913 {
	// BOJ / 1913번 / 달팽이 / 구현 / 실버5
	
	static int[] dr = {1, 0, -1, 0}; // 하, 우, 상, 좌
	static int [] dc = {0, 1, 0, -1};
	static int map[][];
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int k = Integer.parseInt(br.readLine());
		map = new int[n][n];
		int kr = 0;
		int kc = 0;
        
		makeMap(n);
		
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map.length; j++) {
				sb.append(map[i][j]).append(" ");
				if(map[i][j] == k) {
					kr = i;
					kc = j;
				}
			}
			sb.append("\n");
		}
		sb.append(kr+1).append(" ").append(kc+1);
		System.out.println(sb);
	}
	
	// 주어진 달팽이 방향과 거꾸로 삽입
	public static void makeMap(int n) {
		int r = 0;
		int c = 0;
		int count = n*n; 
		int d = 0; // 방향
		
		while(true) {
			if(count == 0) {
				break;
			}
			map[r][c] = count--;
			int nr = r + dr[d];
			int nc = c + dc[d];
			int nd = setDirection(d,n,nr,nc);
			// 방향이 바뀌면 다음 방향을 기준으로 r,c를 업데이트.
			if(nd != d) {
				r = r + dr[nd];
				c = c + dc[nd];
				d = nd;
			}
			else {
				r = nr;
				c = nc;
			}
		}
	}
	
	public static int setDirection(int d, int n, int nr, int nc) {
		// 범위를 벗어났거나
		if(nr >= n || nc >= n || nr < 0 || nc<0) {
			d = (d+1) % 4; 
		}
		// 이후 있을 자리가 이미 값이 있거나
		else if(map[nr][nc] != 0) {
			d = (d+1) %4;
		}
		
		return d;
	}
}

 

피드백 환영합니다.