문제 탐색하기
입력 자료 정리하기
- r은 세로 길이, c는 가로 길이며,
이후 들어오는 원소 값들은 char 타입의 문자 원소로 탐색의 구분이 될 값이다
해결방법 추론
- 이해하면 정말 쉬운 문제다.
50년동안 1년단위로 탐색하는 것도 아니고, 육지 한칸 주위에 바다가 3칸 이상 있으면
50년 후에 육지가 되는 것이 끝이다 - 따라서 이중포문을 돌면서 BFS의 4방 탐색 배열을 이용하여 주위에 바다 칸이
3칸 이상 있는지 확인하고 있다면, 육지를 바다로 만들어주면 된다 - 입력값을 관리하고 있는 배열에 하면 탐색과정이 꼬이므로,
별도의 50년 후 배열을 하나 더 만들어서 그 배열에 저장해주면 쉽게 풀릴 것이다 - 한가지 더 고려해야하는데, 출력값이 조금 특이하다.
- 직사각형 형태로 나올 수 있는 X의 범위를 최대한으로 담는 형태여야 한다
- 이것을 해결하기 위해서는 직사각형의 네 모서리를 구해서
그 범위 만큼만 탐색한 뒤, 출력하면 해결 될 것이다.
단계 분류
- 단계는 크게 4단계, 입력/출력을 제외하면 2단계이다
- 입력단계에서는 현재의 다도해의 상태를 배열에다가 담아준다
- 이후 2번째 단계에서는 50년 후의 다도해의 상태를 배열에 담아준다
- 이어서 3번째 단계에서는 출력을 위한 직사각형의 네 모서리를 구해준다
- 마지막 출력단계에서는 3번째 단게에서 구한 네 모서리를 바탕으로 출력해준다
시간복잡도 계산
- 시간복잡도는 2번째 단계에서 가장 큰 연산이 발생하므로 이 부분만 확인하면 된다
- 2번째 단계에서는 이중포문을 돌며 4방 탐색하므로, r x c x 4의 연산이 발생한다
- 따라서 시간복잡도는 O(r x c x 4)이며, r과 c의 최대 입력크기는 10이므로,
시간제한안에 해당 문제를 해결할 수 있다
코드 설계하기
입력값 상태 관리하기
- r과 c는 변수에서 관리하며, 각 원소 값은 r x c크기의 char타입의 2차원 배열에 보관한다
단계별 설계
단계 1
- 50년 후, 다도해의 상태를 담을 똑같은 r x c 크기의 char 타입의 2차원 배열을 만든다
- 이중포문을 돌면서 입력값을 관리하는 배열의 인덱스를 탐색한다
- 만약 현재 위치의 값이 육지라면 4방 탐색을 하면서 바다의 개수를 세어준다
- 바다의 개수는 인덱스 범위를 벗어나는 경우와 실제 바다 원소인 경우다
- 만약 바다의 개수가 3개 이상이면 50년 후 다도해의 상태를 관리하는 배열에 바다로 저장한다
- 아니라면 육지로 저장하며, 현재 상태가 이미 바다라면 바다로 저장한다
단계 2
- 이제 출력을 위한 직사각형의 범위를 구하기 위해 네 모서리를 구해야한다
- left와 right, top과 bottom 변수를 선언하는데 이름의 반대되는 위치의 값으로 초기화한다
- left는 c, top은 r, right와 bottom 은 -1로 초기화한다.
- 이어서 다시 이중포문을 돌면서 50년 후 다도해 인덱스의 값이 육지라면
left와 top은 더 작은 값으로, bottom과 right는 더 큰 값으로 저장한다 - 이렇게 한다면 육지를 모두 담는 최소한의 출력 범위를 찾을 수 있다
출력 설계
- 이제 찾은 네 모서리를 범위로 하여 출력을 진행한다
- i의 경우 top부터 bottom까지로 탐색하며, j의 경우 left부터 right까지 탐색한다
- 해당 범위내에서 탐색하면서 50년 후 다도해의 인덱스 값을 출력하면 정답이 된다!
정답 코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
char[][] arr = new char[r][c];
for (int i = 0; i < r; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < c; j++) {
arr[i][j] = input[j].charAt(0);
}
}
int[] dx = {0,0,-1,1};
int[] dy = {-1,1,0,0};
char[][] find = new char[r][c];
// 2중포문 돌면서 4방 탐색
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int count = 0;
if(arr[i][j] == 'X'){
for (int k = 0; k < 4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if(ny < 0 || ny >= r || nx < 0 || nx >= c){
count++;
}else{
if(arr[ny][nx] == '.'){
count++;
}
}
}
if(count >= 3){
find[i][j] = '.';
}else{
find[i][j] = 'X';
}
}else{
find[i][j] = '.';
}
}
}
// 직사각형 범위를 위해 좌우 가로, 상하 세로 탐색
int left = c;
int right = -1;
int top = r;
int bottom = -1;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if(find[i][j]== 'X'){
left = Math.min(left, j);
right = Math.max(right, j);
top = Math.min(top, i);
bottom = Math.max(bottom, i);
}
}
}
//위 범위를 기준으로 출력
for (int i = top; i <= bottom; i++) {
for (int j = left; j <= right; j++) {
bw.write(find[i][j]);
}
bw.write("\n");
}
br.close();
bw.close();
}
}
문제 링크
Software Developer