백준 - 바닥 장식(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1388

[문제 설명]

선의 개수를 구하시오

 

[접근 방법]

-모양이면 양옆으로 조회. |모양이면 위아래로 조회

시간복잡도는 어차피 모든 타일을 돌아야하므로 O(NM)이 될 듯.

 

[리팩토링 전 코드]

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        boolean[][] visited = new boolean[N][M];
        char[][] map = new char[N][M];

        for (int row = 0; row < N; row++) {
            map[row] = br.readLine().toCharArray();
        }
        
        System.out.println(search(map,visited));
    }

    private static int search(char[][] map, boolean[][] visited) {
        int sum = 0;
        for (int currentRowPoint = 0; currentRowPoint < map.length; currentRowPoint++) {
            for (int currentColumnPoint = 0; currentColumnPoint < map[currentRowPoint].length; currentColumnPoint++) {
                if (visited[currentRowPoint][currentColumnPoint]) {
                    continue;
                } else {
                    checkSide(currentRowPoint,currentColumnPoint,map,visited);
                    sum++;
                }
            }
        }

        return sum;
    }

    private static void checkSide(int currentRowPoint, int currentColumnPoint, char[][] map, boolean[][] visited) {
        visited[currentRowPoint][currentColumnPoint] = true;
        if (map[currentRowPoint][currentColumnPoint] == '-') {
            // 왼쪽 체크
            int tempColumnPoint = currentColumnPoint-1;
            while (0 <= tempColumnPoint) {
                if (map[currentRowPoint][tempColumnPoint] == '-') {
                    visited[currentRowPoint][tempColumnPoint] = true;
                } else {
                    break;
                }
                tempColumnPoint--;
            }

            tempColumnPoint = currentColumnPoint+1;
            // 오른쪽 체크
            while (tempColumnPoint < map[currentRowPoint].length) {
                if (map[currentRowPoint][tempColumnPoint] == '-') {
                    visited[currentRowPoint][tempColumnPoint] = true;
                } else {
                    break;
                }
                tempColumnPoint++;
            }
        } else {
            // 위쪽 체크
            int tempRowPoint = currentRowPoint-1;
            while (0 <= tempRowPoint) {
                if (map[tempRowPoint][currentColumnPoint] == '|') {
                    visited[tempRowPoint][currentColumnPoint] = true;
                } else {
                    break;
                }
                tempRowPoint--;
            }

            tempRowPoint = currentRowPoint+1;
            // 오른쪽 체크
            while (tempRowPoint < map.length) {
                if (map[tempRowPoint][currentColumnPoint] == '|') {
                    visited[tempRowPoint][currentColumnPoint] = true;
                } else {
                    break;
                }
                tempRowPoint++;
            }
        }
    }
}

위아래 왼쪽 오른쪽을 다 체크했다.

제출하고 생각한 건데, 시작 지점이 0,0으로 고정되어 있으므로 오른쪽을 체크하거나 아래를 체크하면 됐다.

 

[리팩토링 후 코드]

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


public class Main {
    private static int search(char[][] map, boolean[][] visited) {
        int sum = 0;
        for (int currentRowPoint = 0; currentRowPoint < map.length; currentRowPoint++) {
            for (int currentColumnPoint = 0; currentColumnPoint < map[currentRowPoint].length; currentColumnPoint++) {
                if (!visited[currentRowPoint][currentColumnPoint]) {
                    checkSide(currentRowPoint,currentColumnPoint,map,visited);
                    sum++;
                }
            }
        }

        return sum;
    }

    private static void checkSide(int currentRowPoint, int currentColumnPoint, char[][] map, boolean[][] visited) {
        visited[currentRowPoint][currentColumnPoint] = true;
        if (map[currentRowPoint][currentColumnPoint] == '-') {
            // 오른쪽 체크
            int tempColumnPoint = currentColumnPoint+1;
            while (tempColumnPoint < map[currentRowPoint].length) {
                if (map[currentRowPoint][tempColumnPoint] != '-') {
                    break;
                }
                visited[currentRowPoint][tempColumnPoint] = true;
                tempColumnPoint++;
            }
        } else {
            // 아래쪽 체크
            int tempRowPoint = currentRowPoint+1;
            while (tempRowPoint < map.length) {
                if (map[tempRowPoint][currentColumnPoint] != '|') {
                    break;
                }
                visited[tempRowPoint][currentColumnPoint] = true;
                tempRowPoint++;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        boolean[][] visited = new boolean[N][M];
        char[][] map = new char[N][M];

        for (int row = 0; row < N; row++) {
            map[row] = br.readLine().toCharArray();
        }
        
        System.out.println(search(map,visited));
    }
}

오른쪽이랑 아래만 체크하게 코드를 수정했고, if문을 반대로 줘서 코드를 필요없는 코드를 수정했다.