IT Docs

문제 링크 : https://www.acmicpc.net/problem/16926

처음 시도에는 배열의 외각을 돌리는 거 말고는 해결하지 못하였다.

그래서 배열 돌리기의 기초가 되는 백준 달팽이 문제를 풀면서 기초를 다지고 다시 풀었다.

문제를 해결하는 원리를 이해하여 풀었고 어느 정도 힌트를 기억하고 있어서 문제를 푸는데 수월하였다.

이 문제가 어렵게 느껴진다면 달팽이 문제를 풀고 다시 도전하기 바란다.

• nkt-docs.tistory.com/17

배열 돌리기 1의 소스를 아래와 같이 공유한다.

public class 배열돌리기1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		
		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);
		int t = Integer.parseInt(str[2]);
		
		int[][] map = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int min = Math.min(n, m);
		int[] dx = {0, 1, 0, -1};
		int[] dy = {1, 0, -1, 0};

		for(int z = 0; z < t; z++) {
			for(int i = 0; i < min/2; i++) {
				int x = i;
				int y = i;
				int temp = map[x][y];
				int idx = 0;
				
				while(idx < 4) {
					int xx = x + dx[idx], yy = y + dy[idx];
					
					if(xx < i || yy < i || xx > n-i-1 || yy > m-i-1) {
						idx++;
					}else {
						map[x][y] = map[xx][yy];
						x = xx;
						y = yy;
					}
				}
				map[x+1][y] = temp;
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				sb.append(map[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
}

문제 링크 : https://www.acmicpc.net/problem/1913

달팽이 문제는 백준 배열 돌리기 1, 배열 돌리기 문제를 먼저 접하게 되어 풀게 된 문제이다.
배열 돌리기 문제가 너무 어려웠다..
배열 돌리기 유형의 문제를 처음 본 사람이 과연 누군가의 도움 없이 문제를 풀 수 있을까라는 의문을 가지게 되었고 누군가는 단박에 문제를 풀었을 거라는 생각에 나 자신에게 화가 나고 무기력해졌다.
그래도 어쩌겠나 모르면 부딪혀서 경험하고 배우는 수밖에 없다.
그래서 배열 돌리기의 기초 문제인 달팽이 문제를 풀게 되었다.

내가 느낀 감정을 표출하지 않는다면 성장할 수 없다는 생각에 서론이 길었다.

처음 문제를 접했을 때 index가 정사각형의 각 꼭짓점이 되는 부분에 도달했을 때 조건문을 주어 방향을 전환하였다.
하지만 조건문은 특정 영역인 각 꼭짓점인 부분만 동작하도록 되어있어 정사각형의 외각만 숫자를 카운팅 하게 되었다.
그 뒤로는 안쪽의 배열을 어떻게 채워나가야 할지 고민하다 포기하고 사방 탐색을 변형해서 구현하면 된다는 힌트를 얻어 문제 다시 풀었다.

사방 탐색은 나의 위치에서 상, 우, 하, 좌를 탐색하는 구현 방법이어서 이걸 변형해서 인덱스의 끝부분이나 0을 만난다면 방향을 전환하고 달팽이 모양을 만들기 위해 이미 값이 채워져 있다면(map[x][y] != 0) 방향을 전환하도록 구현하였다.

아래와 같이 소스를 공유한다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int t = sc.nextInt();
		
		int[][] map = new int[n][n];
		
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
		
		int cnt = n*n;

		for(int i = 0; i <= n/2; i++) {
			int x = i;
			int y = i;
			int idx = 0;
			
            // 사방 탐색이 시작위치보다 한 칸더 앞서 있기 때문에 시작 위치의 값 삽입
			map[i][i] = cnt--;
			
			while(idx < 4) {
				
				int xx = x + dx[idx], yy = y + dy[idx];

				// 정사각형의 외각에 도달했다면 방향 전환
				if(xx >= n || yy >= n || xx < 0 || yy < 0) {
					idx++;
                // 이미 값이 채워져 있다면 방향 전환
				}else if(map[xx][yy] != 0) {
					idx++;
				}else {
					map[xx][yy] = cnt--;
					x = xx;
					y = yy;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		int x = 0, y = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				int val = map[i][j];
				if(map[i][j] == t) {
					x = i;
					y = j;
				}
                // IDE에서 디버깅시 한눈에 보기 위한 formatting
				// sb.append(String.valueOf(val).length() == 1 ? "0" + val:val).append(" ");
                sb.append(val).append(" ");
			}
			sb.append("\n");
		}
		
		sb.append(x+1).append(" ").append(y+1);
		
		System.out.println(sb.toString());
	}