"십자가 찾기" - 16924번
🎃문제설명
십자가는 가운데에 ''가 있고, 상하좌우 방향으로 모두 같은 길이의 ''가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크거나 같아야 한다.
아래 그림은 크기가 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.
...*...
..*.. ...*...
.*. ..*.. ...*...
*** ***** *******
.*. ..*.. ...*...
..*.. ...*...
...*...크기가 N×M이고, '.'과 '*'로 이루어진 격자판이 주어진다. 이때, 십자가만을 이용해서 격자판과 같은 모양을 만들 수 있는지 구해보자. 십자가는 서로 겹쳐도 된다. 사용할 수 있는 십자가의 개수는 N×M이하이어야 한다. 격자판의 행은 위에서부터 1번, 열은 왼쪽에서부터 1번으로 번호가 매겨져 있다.
입력
첫째 줄에 격자판의 크기 N, M (3 ≤ N, M ≤ 100)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다.
출력
십자가만 이용해서 입력으로 주어진 격자판을 만들 수 없으면 -1을 출력한다.
만들 수 있는 경우에는 필요한 십자가의 수 k(0 ≤ k ≤ N×M)를 출력한다. 다음 k개의 줄에는 그려야 하는 십자가의 정보 x, y, s를 한 줄에 하나씩 출력한다. x는 십자가 중심의 행의 번호, y는 열의 번호, s는 십자가의 크기이다.
가능한 답이 여러가지인 경우에는 아무거나 출력한다.
💾입출력 예
| 입력 | 출력 |
|---|---|
| 6 8 ....*... ...**... ..*****. ...**... ....*... ........ | 3 3 4 1 3 5 2 3 5 1 |
| 5 5 .*... ***. .*** ..**. ..... | 3 2 2 1 3 3 1 3 4 1 |
| 5 5 .*... ***.. .... .... ..... | -1 |
| 3 3 *.* .*. *.* | -1 |
알고리즘 분류
- 구현
- 브루트포스 알고리즘
- 시뮬레이션
🌟문제 이해 및 풀이계획
✏️처음 문제를 봤을 때 잘 이해되지 않아 몇 번씩을 다시 읽어본 후에야 입력과 출력에 대한 이해를 할 수 있었다.. 처음부터 천천히 꼼꼼히 읽는 습관을 들여야 겠다.
✏️사실 모든 십자가에 대해 위,아래,양 옆의 '*' 를 체크하고 가능하면 해당 좌표를 기억하는 방식으로 생각은 했지만 겹치는 부분에 대해 어떻게 생각해야 하는지 막막했다.
✏️그래서 결국 코드 작성은 하지 못하고 강의를 들었다.
강의내용
✔️사용할 수 있는 십자가 개수는 NM이하기 때문에 모든 '*'에 대해 십자가 중앙이라고 생각하고 가장 큰 십자가를 찾아본다.
✔️예를 들면, 가장 큰 십자가가 3이라면 1, 2는 당연히 그릴 수 있으므로 가장 큰 3만 구하는 것이다.
✍🏻내 코드2 + 강의
package BOJ;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
/*
* 2021.12.05 daily algo/commit
*
* brute force
*/
public class boj_16924 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
char[][] grid = new char[N][M];
boolean[][] visited = new boolean[N][M];
for(int i=0; i<N; i++) {
String line = sc.next();
for(int j=0; j<M; j++) {
grid[i][j] = line.charAt(j);
}
}
ArrayList<Integer> x = new ArrayList<Integer>();
ArrayList<Integer> y = new ArrayList<Integer>();
ArrayList<Integer> s = new ArrayList<Integer>();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
int size = 0; // 십자가 크기
if(grid[i][j] == '*') {
for(int k=1; ; k++) {
if(i-k >= 0 && i+k < N && j-k >=0 && j+k < M) {
if(grid[i-k][j] == '*' && grid[i+k][j] == '*' && grid[i][j-k] == '*' && grid[i][j+k] == '*') {
size = k;
}
else break;
}
else break;
}
}
if(size > 0) {
x.add(i+1);
y.add(j+1);
s.add(size);
visited[i][j] = true;
for(int k=1; k<=size; k++) {
visited[i+k][j] = true;
visited[i-k][j] = true;
visited[i][j+k] = true;
visited[i][j-k] = true;
}
}
}
}
// 격자판 만들 수 없을 때
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(grid[i][j] == '*' && visited[i][j] == false) {
System.out.println(-1);
System.exit(0);
}
}
}
// 격자판 만들 수 있을 때
System.out.println(x.size());
for(int i=0; i<x.size(); i++) {
for(int j=s.get(i); j>=1; j--) {
System.out.println(x.get(i)+" "+y.get(i)+" "+j);
}
}
sc.close();
}
}
💡System.exit(0)을 이용하여 -1을 리턴하고 바로 종료한다.
💡visited배열을 추가하여 십자가를 만든 곳을 true로 하고, '*'인데 false인 곳이 있다면 격자판을 만들 수 없으므로 -1을 리턴한다.
