[백준] G3 2933 미네랄 (java)

www.acmicpc.net/problem/2933

2933번: 미네랄

 

 

풀이1 (메모리 초과)

 

1) 큐에 막대기 정보를 담음

2) 큐가 빌 때까지 poll() 하면서 맵을 부숨

3) bfs를 돌려서 붙어있는 덩어리를 list에 담음

4) list에서 열(c)중에 가장 행(r)이 높은 애들만 따로 list2에 담음 

5) list2중에서 바닥 or 미네랄과의 최소거리 min을 구함

6) list를 min만큼 아래로 내림

7) 반복

 

주의사항

 

1) 방문체크하는 배열의 초기화 위치

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G3_2933_미네랄 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int R, C, N;
	static boolean isVisited[][], dir;
	static char map[][];
	static Queue<Integer> queue = new LinkedList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
//		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		R = Integer.parseInt(tokens.nextToken());
		C = Integer.parseInt(tokens.nextToken());
		map = new char[R][C];
		for(int r=0; r<R; r++) {
			String line = input.readLine();
			for(int c=0; c<C; c++) {
				map[r][c] = line.charAt(c);
			}	
		}
		N = Integer.parseInt(input.readLine());
		tokens = new StringTokenizer(input.readLine());
		for(int i=0; i<N; i++) {
			int stick = Integer.parseInt(tokens.nextToken());
			queue.offer(stick);
		}
		
		isVisited = new boolean[R][C];
		while(!queue.isEmpty()) {
			int front = R-queue.poll(); // 거꾸로 봐야함
			stickThrow(front, dir); // 맵을 부숨. dir = false : 좌, true : 우
			for(int r=0; r<R; r++) {
				for(int c=0; c<C; c++) {
					for(int i=0; i<R; i++) {
						for(int j=0; j<C; j++) {
							isVisited[i][j] = false;
						}	
					}
					if(!isVisited[r][c] && map[r][c] == 'x') {
						bfs(r,c);
					}
				}	
			}
		}
		for(char x[] : map) {
			System.out.println(Arrays.toString(x));
		}
	}

	private static void bfs(int r, int c) {
		
		Queue<Node> q = new LinkedList<>();
		List<Node> list = new ArrayList<>();
		list.add(new Node(r, c));
		q.offer(new Node(r, c));
		isVisited[r][c] = true;
		boolean flag = false;
		while(!q.isEmpty()) {
			Node front = q.poll();
			if(front.r == R-1) {
				flag = true;
			}
			for(int d=0; d<4; d++) {
				int nr = front.r + dr[d];
				int nc = front.c + dc[d];
				if(isIn(nr, nc) && !isVisited[nr][nc] && map[nr][nc] == 'x') {
					q.offer(new Node(nr, nc));
					isVisited[nr][nc] = true;
					list.add(new Node(nr, nc));
				}
			}
		}
		
		if(!flag) {
			
			List<Node> list2 = new ArrayList<>(); // 열중에 가장 r이 큰값만 담을 리스트
			
			Collections.sort(list);
			int cs = -1;
			for(int i=0; i<list.size(); i++) {
				if(list.get(i).c != cs) {
					cs = list.get(i).c; 
					list2.add(list.get(i));
				}
			}
			int min = Integer.MAX_VALUE; // 차이값의 최소 : 내려갈 칸 수
			for(int i=0; i<list2.size(); i++) {
				int row = 0;
				for(row= 1; row<R; row++) {
					if(!isIn(list2.get(i).r + row, list2.get(i).c) ||  map[list2.get(i).r + row][list2.get(i).c] == 'x') {
						continue;
					}
					if(min > row-1) {
						min = row;
					}
				}
			}
			if(min != 0) { // 내려갈 칸수가 0이아니면 min만큼 내릴거임 
				for(int i=0; i<list.size(); i++) {
					map[list.get(i).r][list.get(i).c] = '.';
				}
				for(int i=0; i<list.size(); i++) {
					map[list.get(i).r+min][list.get(i).c] = 'x';
				}
			}
		}
		
		
		
	}
	
	static class Node implements Comparable<Node>{
		int r;
		int c;
		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + "]";
		}
		@Override
		public int compareTo(Node o) {
			if(this.c == o.c) {
				return Integer.compare(o.r, this.r);
			}
			return Integer.compare(this.c, o.c);
		}
	}
	
	static int dr[] = {0,0,1,-1};
	static int dc[] = {1,-1,0,0};
	
	static boolean isIn(int r, int c) {
		return(r>=0 && c>=0 && r<R && c<C);
	}
	
	private static void stickThrow(int front, boolean turn) {
		if(!turn) { // -> 방향
			for(int c=0; c<C; c++) {
				if(map[front][c] == 'x') {
					map[front][c] = '.';
					break;
				}
			}
		}else { // <- 방향
			for(int c=C-1; c>=0; c--) {
				if(map[front][c] == 'x') {
					map[front][c] = '.';
					break;
				}
			}
		}
		dir = !dir;
	}

	static String src =
			"8 8\r\n" + 
			"........\r\n" + 
			"........\r\n" + 
			"...x.xx.\r\n" + 
			"...xxx..\r\n" + 
			"..xxx...\r\n" + 
			"..x.xxx.\r\n" + 
			"..x...x.\r\n" + 
			".xxx..x.\r\n" + 
			"5\r\n" + 
			"6 6 4 3 1";
}

 

 

풀이2

 

1) 큐에 막대기 정보를 담음

2) 큐가 빌 때까지 poll() 하면서 맵을 부숨

3) 바닥에 닿아 있는 애들을 모두 큐에 담음

4) bfs를 돌림. 

5) 이제 방문체크가 안되면서 x인 애들은 떨어져야할 덩어리이다. 걔네들을 list에 담음

6) list에 포함된 미네랄을 전부 '.' 으로 바꿈

7) list에서 바닥 or 미네랄까지의 거리의 최솟값 min을 구함

8) list에 포함된 미네랄을 전부 min 만큼 아래로 이동해 'x' 로 바꿈

9) 반복

 

 

주의사항

 

1) 6번 안하면 안됨

2) 출력할때 공백문자 있으면 안됨.. <- 이거때매 왜 틀렸는지 한참 헤맸다..

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G3_2933_미네랄 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int R, C, N;
	static boolean isVisited[][], dir;
	static char map[][];
	static Queue<Integer> queue = new LinkedList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		R = Integer.parseInt(tokens.nextToken());
		C = Integer.parseInt(tokens.nextToken());
		
		map = new char[R][C];
		for(int r=0; r<R; r++) {
			String line = input.readLine();
			for(int c=0; c<C; c++) {
				map[r][c] = line.charAt(c);
			}	
		}
		N = Integer.parseInt(input.readLine());
		tokens = new StringTokenizer(input.readLine());
		for(int i=0; i<N; i++) {
			int stick = Integer.parseInt(tokens.nextToken());
			queue.offer(stick);
		}
		
		while(!queue.isEmpty()) {
			int front = R-queue.poll(); // 거꾸로 봐야함
			stickThrow(front, dir); // 맵을 부숨. dir = false : 좌, true : 우
			Queue<Node> q = new LinkedList<>();
			isVisited = new boolean[R][C];
			for(int c=0; c<C;c++) {
				if(map[R-1][c] == 'x') {
					q.offer(new Node(R-1, c));
					isVisited[R-1][c] = true;
				}
			}
			while(!q.isEmpty()) {
				Node node = q.poll();
				for(int d=0; d<4; d++) {
					int nr = node.r + dr[d];
					int nc = node.c + dc[d];
					if(isIn(nr, nc) && !isVisited[nr][nc] && map[nr][nc] == 'x') {
						q.offer(new Node(nr, nc));
						isVisited[nr][nc] = true;
					}
				}
			}
			List<Node> list = new ArrayList<>();
			for(int r=0; r<R; r++) {
				for(int c=0; c<C; c++) {
					if(!isVisited[r][c] && map[r][c] == 'x') {
						list.add(new Node(r, c));
					}
				}	
			}
			if(list.size() != 0) {
				drop(list);// 리스트를 바닥또는 x에 닿을때까지 내린다.
			}
			
		}
		for(int r=0; r<R; r++) {
			for(int c=0; c<C; c++) {
				System.out.print(map[r][c]);
			}
			System.out.println();
		}
	}

	
	private static void drop(List<Node> list) {
		for(Node node : list) {
			map[node.r][node.c] = '.';
		}
		int cnt = 0;
		outer : for(int i=1; i<R; i++) {
			for(Node node : list) {
				if(node.r+i>=R || map[node.r+i][node.c] == 'x') {
					break outer;
				}
			}
			cnt = i;
		}
		for(Node node : list) {
			map[node.r+cnt][node.c] = 'x';
		}
		
	}


	static class Node {
		int r;
		int c;
		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	
	static int dr[] = {0,0,1,-1};
	static int dc[] = {1,-1,0,0};
	
	static boolean isIn(int r, int c) {
		return(r>=0 && c>=0 && r<R && c<C);
	}
	
	private static void stickThrow(int front, boolean turn) {
		if(!turn) { // -> 방향
			for(int c=0; c<C; c++) {
				if(map[front][c] == 'x') {
					map[front][c] = '.';
					break;
				}
			}
		}else { // <- 방향
			for(int c=C-1; c>=0; c--) {
				if(map[front][c] == 'x') {
					map[front][c] = '.';
					break;
				}
			}
		}
		dir = !dir;
	}

	static String src =
			"10 10\r\n" + 
			"xxxxxxxxxx\r\n" + 
			"....x.....\r\n" + 
			"...xxx....\r\n" + 
			".....x....\r\n" + 
			"....xx....\r\n" + 
			".....x....\r\n" + 
			"xxxxxx....\r\n" + 
			"..x.......\r\n" + 
			".xxxx.....\r\n" + 
			"...xxxxxxx\r\n" + 
			"10\r\n" + 
			"9 8 7 6 5 4 3 2 1 1";
}

 

 

후기

 

문제에서 "두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다." 라는 문구를 잘 이해했다면 풀이1의 개고생은 하지 않았을 것이다. 문제를 똑바로 읽고 이해한 후에 푸는 습관을 가져야 한다는 교훈을 얻은 좋은 계기였다.