IT Docs

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

이 문제는 배열 돌리기 1을 먼저 푼 후 접근하였다.

nkt-docs.tistory.com/18

두 문제의 차이점은 기본 로직은 동일 하나 어떤 값을 돌릴 것인지의 차이가 있다.

문제의 핵심

1. 2차원 정수 배열의 크기는 홀수 X 홀수이기 때문에 항상 가운데 지점이 존재한다.

1. 2차원 정수 배열의 크기는 홀수 X 홀수이기 때문에 항상 가운데 지점이 존재한다.
2. 배열의 첫 번째 트랙부터 가운데 지점까지(N/2) 반목문을 실행한다.
3. 가운데 지점에서 몇 번째 트랙인지를 체크하여 배열의 어떤 값을 돌릴지 구현한다.
   1. N이 5일 때, 첫 번째 트랙(가장 외곽)은 N/2 - x(행)을 계산하여 돌릴 값을 선택한다.
4. 각도의 값이 0보다 작으면 +8을 하여 항상 오른쪽 방향으로만 돌아가도록 구현한다.
   1. -45도일 경우, -45/45 == -1이므로 +8을 하여 7번 만큼 오른쪽으로 돌렸을 때 왼쪽으로 1번(-1) 돌린 위치가 된다.
5. 항상 오른쪽으로 배열을 돌리지만 실제로는 왼쪽(0,0 기준 하, 좌, 상, 우)으로 돌면서 값을 이동  시킨다.

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

public class 배열돌리기 {
	public static int N;
	public static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int t = Integer.parseInt(br.readLine());
		
		for(int z = 0; z < t; z++) {
			String[] str = br.readLine().split(" ");
			
			N = Integer.parseInt(str[0]);
			int c = Integer.parseInt(str[1]);
			
			map = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			if(c%360 != 0 ) {
				move(c/45);
			}
			
			StringBuilder sb = new StringBuilder();
			
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
                	// 움직인 배열을 보기 좋게 출력
					// sb.append(map[i][j] <= 9 ? "0"+map[i][j]:map[i][j]).append(" ");
                    sb.append(map[i][j]).append(" ");
				}
				sb.append("\n");
			}
			
			bw.write(sb.toString());
		}
		
		bw.flush();
		bw.close();
	}
	
	public static void move(int c) {
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
        // 가운데 지점
		int p = N/2;
		
		if(c < 0) c += 8;
		
		for(int i = 0; i < c; i ++) {
			for(int j = 0; j < N/2; j++) {				
				int x = j;
				int y = j;		
				int idx = 0;
				int temp = map[x][y];
				
				while(idx < 4) {
					int mx = dx[idx]*(p-j);
					int my = dy[idx]*(p-j);
					int xx = x + mx, yy = y + my;
					
					if(xx < j || yy < j || xx > N-j-1 || yy > N-j-1) {
						idx++;
					}else {
						map[x][y] = map[xx][yy];
						x = xx;
						y = yy;
					}
				}
                // 마지막 위치에 첫번째 값을 할당
				map[x][y+(p-j)] = temp;
			}
		}
	}
}

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

이 문제의 등급이 골드 5라서 문제를 읽기도 전에 겁을 먹었다..

그래도 스터디 시간에 풀어야 하기 때문에 문제 풀기 시작했고 생각했던 것보다 어렵지 않아 빠른 시간 안에 해결했다.

어려운 문제라고 생각했는데 내가 의도한 대로 문제가 잘 풀려나가서 최근 문제 풀면서 가장 크게 뿌듯함을 느끼게 해준 문제다.

내가 구현한 핵심 로직은 각 행의 막혀있는 지점의 위치를 찾아서 반복문을 통해 1번 지점과 2번 지점 사이의 공간에 물을 채우는 로직이다.

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

public class 빗물 {
	public static class Node {
		int x, y;
		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	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[][] map = new int[n][m];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int idx = 0;
		while(st.hasMoreTokens()) {
			int y = Integer.parseInt(st.nextToken());
			for(int i = 0; i <= y-1; i++) {
				map[i][idx] = 1;
			}
			idx++;
		}
		
		for(int i = 0; i < n; i++) {
			List<Node> list = new ArrayList<>();
			for(int j = 0; j < m; j++) {
				if(map[i][j] == 1) {
					list.add(new Node(i, j));
				}
			}
			
            // 행에 벽이 2개 이상일때 벽과 벽 사이의 공간에 빗물(2) 채우기
			if(list.size() >= 2) {
				for(int j = 0; j < list.size()-1; j++) {
					for(int k = list.get(j).y+1; k < list.get(j+1).y; k++) {
						map[i][k] = 2;
					}
				}
			}
			list = new ArrayList<>();
		}
		
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				int v = map[i][j];
				if(v == 2) cnt++;
			}
		}
		
		System.out.println(cnt);
	}
}

문제 링크 : 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());
	}