백준 14711 타일 뒤집기 java (dp)

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

14711번: 타일 뒤집기 (Easy)

 

 

 

아이디어를 얻기가 힘든 문제.

 

'윗 줄은 미리 답을 정해놓고 간다'는 생각을 가지고 임해야 한다. 실제로 가장 맨 윗줄은 이미 입력에서 주어진다.

 

"가능한 모든 입력에 대해 답이 유일하게 존재함이 보장된다."라는 말이 문제 말미 쯤에 있는데,

 

이것 또한 중요하다. 맵이 완성된 시점의 모든 '#'들을 나중에 동생이 뒤집을 것이기 때문에, 완성된 모습을 계속 복기하면서 코드를 짜면 좋다.

 

 

 

뒤집힌 것을 또 뒤집는 경우가 있기 때문에 visited 배열을 이용해서 계속 뒤집어 준다고 가정한다.

boolean[][] visited = new boolean[n][n];

 

 

 

먼저 좌/우/하 세 방향에 대해 뒤집기를 실행해주고,

if(map[i].charAt(j) == '#'){
    if(0 < j){ // 좌
        visited[i][j-1] = !visited[i][j-1]; // 방문 no --> 방문 처리, 방문 ok --> 비방문 처리
    }
    if(j < n-1){ // 우
        visited[i][j+1] = !visited[i][j+1];
    }
    if(i < n-1){ // 하
        visited[i+1][j] = !visited[i+1][j];
    }
}

 

 

 

마지막으로 밑에 줄에 있는 녀석을 뒤집었을 때 윗줄 '상' 방향이 영향을 받으므로 이것에 대해 처리를 해야 한다.

바로 윗칸이 '#'으로 판명났을 경우(모든 방문을 마쳤을 때 '#'인 경우) 아랫칸을 미리 뒤집어 놓는다.

for(int j=0; j<n; ++j){
    if(visited[i][j]) map[i+1].append('#');
    else map[i+1].append('.');
}

 

 

 

이런 식으로 짜면 맨 마지막 줄이 하나 더 완성되므로 처음에 n+1로 map을 초기화해준다.

StringBuilder[] map = new StringBuilder[n+1];

 

마지막에 한줄이 더 추가되더라도, 따로 답으로 사용할 StringBuilder ans를 준비해놓으면 된다.

StringBuilder ans = new StringBuilder();

 

이렇게 해서 로직 한번이 실행되면 계속 줄 추가

ans.append(map[i]).append("\n");

 

 

 

# 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder[] map = new StringBuilder[n+1];
        for(int i=0; i<n+1; ++i){
            map[i] = new StringBuilder();
        }
        map[0].append(br.readLine()); // 첫 줄 입력
        boolean[][] visited = new boolean[n][n];

        StringBuilder ans = new StringBuilder();
        for (int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                if(map[i].charAt(j) == '#'){
                    if(0 < j){ // 좌
                        visited[i][j-1] = !visited[i][j-1]; // 방문 no --> 방문 처리, 방문 ok --> 비방문 처리
                    }
                    if(j < n-1){ // 우
                        visited[i][j+1] = !visited[i][j+1];
                    }
                    if(i < n-1){ // 하
                        visited[i+1][j] = !visited[i+1][j];
                    }
                }
            }

            for(int j=0; j<n; ++j){
                if(visited[i][j]) map[i+1].append('#');
                else map[i+1].append('.');
            }

            ans.append(map[i]).append("\n");
        }

        System.out.print(ans);

    }
}