[백준] S2 16924 십자가 찾기 (java)

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

16924번: 십자가 찾기

 

풀이

 

0) 십자가체크를 위한 isChecked[][] 배열, 결과값을 저장하기위한 List, List에 넣을 자료형 Cross를 만든다.

1) 코너에 * 이 있으면 무조건 -1

2) 테두리에선 십자가를 만들 수 없다.

3) * 이 있는 모든 곳에서 십자가를 만들어본다.

3-1) 상, 하, 좌, 우로 뻗어서 가장 짧은 거리 size 를 구한다.

3-2) size가 0보다 크면 1부터 size 까지 십자가를 만들 수 있다. 리스트에 중앙좌표와 사이즈를 넣는다. 체크 배열도 true로 설정한다.

4) 다 돌고 체크배열을 확인한다.

4-1) 체크 배열에 하나라도 false가 있을경우 십자가만 이용해서 격자판을 만들 수 없는것이다. -1 출력.

4-2) 체크 배열이 모두 true 일경우 십자가만 이용해서 격자판을 만들 수 있다는 뜻이다. 리스트의 크기와 내용을 출력.

 

주의사항

 

1) print로 하면 겁나 오래걸린다. BufferedWriter로 출력하자.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_S2_16924_십자가찾기 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer tokens;
	static int N,M;
	static char map[][];
	static boolean isChecked[][];
	static List<Cross> list = new ArrayList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new char[N][M];
		isChecked = new boolean[N][M];
		for(int r=0; r<N; r++) {
			String line = input.readLine();
			for(int c=0; c<M; c++) {
				map[r][c] = line.charAt(c);
				if(line.charAt(c) == '.') {
					isChecked[r][c] = true;
				}
			}
		}
		if(map[0][0] == '*' || map[0][M-1] == '*' || map[N-1][0] == '*' || map[N-1][M-1] == '*') {
			output.append("-1");
		}else {
			for(int r=1; r<N-1; r++) {
				for(int c=1; c<M-1; c++) {
					if(map[r][c] == '*') {
						fillCross(r,c);
					}
				}	
			}
			boolean flag = false;
			outer : for(int r=0; r<N; r++) {
				for(int c=0; c<M; c++) {
					if(!isChecked[r][c]) {
						flag = true;
						break outer;
					}
				}	
			}
			if(flag) {
				output.append("-1");
			}else {
				output.append(list.size() +"\n");
				for(Cross x : list) {
					output.append(x.r+" "+x.c+" "+x.k+"\n");
				}
			}
		}
		output.close();
	}
	private static void fillCross(int r, int c) {
		int size = Integer.MAX_VALUE;
		
		for(int d=0; d<4; d++) {
			int nr = r;
			int nc = c;
			int cnt = 0;
			while(true) {
				nr = nr+dr[d];
				nc = nc+dc[d];
				if(!isIn(nr, nc) || (isIn(nr, nc) && map[nr][nc] == '.')) {
					if(size > cnt) {
						size = cnt;
					}
					break;
				}
				cnt++;
			}
		}
		if(size!=0) {
			for(int nr=r-size; nr<=r+size; nr++) {
				isChecked[nr][c] = true;
			}
			for(int nc=c-size; nc<=c+size; nc++) {
				isChecked[r][nc] = true;
			}
			for(int k=size; k>0; k--) {
				list.add(new Cross(r+1, c+1, k));
			}
		}
		
	}
	static int dr[] = {-1,0,1,0};
	static int dc[] = {0,1,0,-1};
	static boolean isIn(int r, int c){
		return (r>=0 && r<N && c>=0 && c<M);
	}
	
	static class Cross{
		int r;
		int c;
		int k;
		public Cross(int r, int c, int k) {
			super();
			this.r = r;
			this.c = c;
			this.k = k;
		}
	}
	static String src =
			"6 8\r\n"
			+ "....*...\r\n"
			+ "...**...\r\n"
			+ "..*****.\r\n"
			+ "...**...\r\n"
			+ "....*...\r\n"
			+ "........";
}

 

후기

 

 출력때문에 시간이 오래걸리는지 몰라서 1시간동안 다시 풀었다... BufferedWriter를 생활화해야겠다. 저번에도 한번 이랬던거 같은데.. 그와 별개로 비효율 적인 부분이 조금있었지만 다시 푸는 도중에 좀 더 다듬을 수 있었다.