IT Docs

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

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

백준 7576 토마토 문제를 풀고 난 후에 시도한 문제라서 쉬울 거라 생각하고 문제를 접근했다.

7576 토마토는 2차원 문제라면 7569 토마토는 3차원 문제였다.

알고 있는 유형의 문제라서 그런지 너무 쉽게 생각하여 입력 방식에 대해 잘못 구현했다.

첫 시도는 틀렸습니다를 받았다. 문제를 다시 정독한 후 입력 방식을 바꾸고 문제를 해결했다.

구현에 대해서는 어렵지 않았지만 문제를 파악하는데 실수가 있었다.

알고 있는 유형의 문제라도 빠른 해결을 위해 꼼꼼히 읽어보자!!

아래와 같이 구현 소스를 공유합니다.

public class 토마토 {
	public static class Node {
		int x, y, h, s;
		Node(int x, int y, int h, int s) {
			this.x = x;
			this.y = y;
			this.h = h;
			this.s = s;
		}
	}
	public static int X, Y, H, cnt;
	public static int[][][] arr;
	public static boolean[][][] visit;
	public static Queue<Node> que = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		
		Y = Integer.parseInt(str[0]);
		X = Integer.parseInt(str[1]);
		H = Integer.parseInt(str[2]);
		
		arr = new int[X][Y][H];
		visit = new boolean[X][Y][H];
		
		boolean isSuccessed = true;
		
		for (int f = 0; f < H; f++) {
			for (int i = 0; i < X; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < Y; j++) {
					int v = Integer.parseInt(st.nextToken());
					if(v == 0) isSuccessed = false;
					if(v == 1) {
						que.add(new Node(i, j, f, 0));
						visit[i][j][f] = true;
					}
					arr[i][j][f] = v;
				}
			}
		}
		
		if(isSuccessed) {
			System.out.println("0");
		}else {
			bfs();
			
			boolean isCompleted = true;
			
			for (int f = 0; f < H; f++) {
				for (int i = 0; i < X; i++) {
					for (int j = 0; j < Y; j++) {
						int v = arr[i][j][f];
						if(v == 0) isCompleted = false;
					}
				}
			}
			
			if(isCompleted) {
				System.out.println(cnt-1);
			}else {
				System.out.println("-1");
			}
			
		}
	}
	
	public static void bfs() {
		int[] dx = {0, -1, 0, 1, 0, 0};
		int[] dy = {-1, 0, 1, 0, 0, 0};
		int[] dh = {0, 0, 0, 0, -1, 1};
		
		while(!que.isEmpty()) {
			int size = que.size();
			cnt++;
			for (int i = 0; i < size; i++) {				
				Node node = que.poll();
				
				for (int j = 0; j < 6; j++) {
					int xx = node.x + dx[j], yy = node.y + dy[j], hh = node.h + dh[j];
					if(xx < X && yy < Y && hh < H && xx >= 0 && yy >= 0 && hh >= 0) {
						if(!visit[xx][yy][hh] && arr[xx][yy][hh] == 0) {
							visit[xx][yy][hh] = true;
							arr[xx][yy][hh] = node.s + 1;
							que.add(new Node(xx, yy, hh, node.s + 1));
						}
					}
				}
			}
		}
 	}
 }