[백준] code.plus(브루트 포스 Part 1,JAVA)16924번, 십자가 찾기

문제 링크

16924번: 십자가 찾기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

 

이 문제에 핵심은

 

1. 십자가를 이용해서 격자판을 만들어야 합니다.

2. 만들 수 있으면 사용한 십자가 개수 및 위치와 크기를 출력하고 없으면 -1을 출력합니다.

3. 십자가는 상하좌우로 크기만큼 길어집니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 십자가를 공간에 놓을 수 있는 모든 경우를 넣어서 격자판이 만들어봅니다.

 

3. 격자판을 만들었으면 사용한 십자가 정보를 출력, 만들지 못하면 -1을 결과로 출력합니다.

 

 

십자가

 

크기 1

	*
*	*(중심)	*
	*

 

크기 2

		*
		*
*	*	*(중심)	*	*
		*
		*

십자가의 크기에 따라 중심에서 증가합니다.

 

십자가를 놓으려는 중심이 되려면 반드시 상하좌우에 *가 존재해야 합니다.

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 6

M = 8

.	.	.	.	*	.	.	.
.	.	.	*	*	.	.	.
.	.	*	*	*	*	*	.
.	.	.	*	*	.	.	.
.	.	.	.	*	.	.	.
.	.	.	.	.	.	.	.

 

2. 십자가를 공간에 놓을 수 있는 모든 경우를 넣어서 격자판이 만들어봅니다.

 

십자가의 중심이 될 수 있는 공간

(3, 4) , (3, 5)

 

십자가의 중심에서 만들 수 있는 최대의 십자가 크기를 만들어봅니다.

(3, 4)의 만들 수 있는 최대 십자가 크기 : 1

(3, 5)의 만들 수 있는 최대 십자가 크기 : 2

 

십자가를 이용해 만든 격자판

.	.	.	.	*	.	.	.
.	.	.	*	*	.	.	.
.	.	*	*	*	*	*	.
.	.	.	*	*	.	.	.
.	.	.	.	*	.	.	.
.	.	.	.	.	.	.	.

 

3. 격자판을 만들었으면 사용한 십자가 정보를 출력, 만들지 못하면 -1을 결과로 출력합니다.

 

십자가를 이용해서 만든 격자판과 입력으로 준 격자판이 같기 때문에 십자가의 정보들을 출력하겠습니다.

 

십자가 개수 : 2

사용한 십자가 :

3, 4, 1

3, 5, 2

 

결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 입력된 값을 띄어쓰기 기준 나누었습니다.
• start을 실행하여 격자판을 십자가로 채울 수 있는지 확인합니다.
• 격자판을 채웠다면 십자가의 정보, 채우지 못하면 -1을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• start함수는 격자판을 탐색하며 채울 수 있는 십자가를 채웠습니다.
• search함수는 해당 칸이 십자가 중심이 되는지 확인 및 최대 크기를 구합니다.
• sizeCal함수는 십자가 중심으로 각 방향의 최대 크기를 구합니다.
• mapCheck함수는 격자판이 십자가로 채워졌는지 확인합니다. 
• inSpace함수는 이동하려는 칸이 격자판에 존재하는지 확인합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    //십자가 정보 클래스
    static class info{
        int x, y, size;
        public info(int x, int y, int size) {
            this.x = x;
            this.y = y;
            this.size = size;
        }
    }
    static int N,M, scale;
    static char[][] map;	//격자판 정보 배열
    static boolean[][] visited;		//방문 확인 배열
    static ArrayList<info> answer = new ArrayList<>();
    static int[] dx = {-1, 1, 0, 0};	//상하좌우 X변경값
    static int[] dy = {0, 0, -1, 1};	//상하좌우 Y변경값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        visited = new boolean[N][M];
        //격자판 정보 저장
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<M;j++)
                map[i][j] = str.charAt(j);
        }
        start();	//격자판 십자가로 채울 수 있는지 탐색
        if(mapCheck()){	//격자판 만들었을 때
            //십자가 정보 BufferedWriter 저장
            bw.write(answer.size() + "\n");
            for(info cur : answer)
                bw.write(cur.x + " " + cur.y + " " + cur.size +"\n");
        }else	//격자판 만들지 못할 때
            bw.write("-1");

        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //입력된 격자판을 십자가로 모두 채울 수 있는지 찾는 함수
    static void start(){
        for(int i=1;i<N-1;i++){
            for(int j=1;j<M-1;j++){
                if(map[i][j] =='.')	// .은 중심이 되지 못함
                    continue;
                if(search(j, i))	//십자가 가능한지 탐색
                    if(scale != Integer.MAX_VALUE){	//십자가 될 때 십자가 정보 저장
                        answer.add(new info(i+1,j+1, scale));
                        for(int s=1;s<=scale;s++){
                            visited[i-s][j] = true;
                            visited[i+s][j] = true;
                            visited[i][j-s] = true;
                            visited[i][j+s] = true;
                        }
                    }
            }
        }
    }
    //십자가 중심이 되는지 확인 및 크기를 구하는 함수 호출하는 함수
    static boolean search(int x, int y){
        for(int i=0;i<4;i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
            if(map[tempY][tempX]=='.')
                return false;
        }
        visited[y][x] = true;
        scale = Integer.MAX_VALUE;
        //상하좌우 방향으로 이동하며 만들 수 있는 최대 크기 구하기
        sizeCal(x, y, 0);
        sizeCal(x, y, 1);
        sizeCal(x, y, 2);
        sizeCal(x, y, 3);
        return true;
    }
    //각 방향으로 나아가 십자가의 최대 크기를 구하는 함수
    static void sizeCal(int x, int y, int d){
        int count = 0;
        while(true){
            int tempX = x + dx[d];
            int tempY = y + dy[d];
            if(!inSpace(tempX,tempY) || map[tempY][tempX]=='.')
                break;
            count+=1;
            x = tempX;
            y = tempY;
        }
        scale = Math.min(scale, count);
    }
    //입력된 격자판과 동일한지 확인하는 함수
    static boolean mapCheck(){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++)
                if(map[i][j]=='*' && !visited[i][j])
                    return false;
        }
        return true;
    }
    //이동하려는 칸이 격자판에 존재하는지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x>=0 && y>=0 && x<M && y<N)
            return true;
        return false;
    }
}