[JAVA] 1388번 - 바닥 장식

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

 

1. DFS, BFS 사용안하고 그냥 품

-> 몇개 그리다보면 감이 오는데 경우를 나눠서 행에서 -의 갯수를 체크하고 열에서 | 갯수를 체크해서 더했다

시간복잡도: O(n * m)

 

2. DFS 사용

 

DFS가 필요한 이유

 

• 연결된 그룹 탐색: DFS는 배열이나 그래프에서 연결된 모든 노드를 탐색할 때 매우 효율적, 우리가 구해야 하는 것은 연결된 '-'나 '|'의 그룹 수, 이 문제는 연결된 그룹을 탐색하는 문제로 바꿔 생각할 수 있다

 

추가로 필요한것 : 방문 여부(visited): DFS를 수행할 때 이미 방문한 위치를 기록하는 n x m 크기의 2차원 불리언 배열. 이 배열을 통해 중복 방문을 방지

 

이어져 있는 타일의 끝까지 간 이후 카운트를 해주면 된다. 

'-'가 연속해서 나타나는 경우, 같은 행에서만 연결 된다 따라서 -일 경우에는 오른쪽으로만 이동하면 된다

'|'는 같은 열에서만 연결된다, 따라서 |일 경우에는 아래로만 이동 하면된다.

재귀적호출을 이용하였다

시간복잡도 : O(n * m) 이지만 각 크기가 최대 50이라서 시간내에 가능하다 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. 각 배열을 문자로 채워준다

2. 이중반복문을 돌면서 dfs메서드를 실행한다

3. 메서드를 한번 실행하면 카운트한다

4. 출력

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

1. 행,열 갯수 더함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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());
    	char arr[][] = new char[n][m];

    	//문자 입력받기 
    	for (int i = 0; i < n; i++) {  
    		String str = br.readLine();
            for (int j = 0; j < m; j++) {    
                arr[i][j] =  str.charAt(j);    
            }
        }
    	
    	int row=0;
    	int col = 0;
    	for(int i = 0; i < n; i++) {
            boolean inSequence = false; 
            for(int j = 0; j < m; j++) {
                if(arr[i][j] == '-') {
                    if(!inSequence) {
                        row++;
                        inSequence = true;
                    }
                } else {
                    inSequence = false;
                }
            }
        }
        
        // 열에서 연속된 '|' 블록 계산
        for(int j = 0; j < m; j++) {
            boolean inSequence = false; 
            for(int i = 0; i < n; i++) {
                if(arr[i][j] == '|') {  
                    if(!inSequence) {
                        col++;
                        inSequence = true;
                    }
                } else {
                    inSequence = false;
                }
            }
        }
    	
    	System.out.println(row+col);
	}
    
}

2. dfs이용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int n, m;
	static boolean[][] isVisited;
	static char arr[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
             
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
    	arr = new char[n][m];
    	isVisited = new boolean[n][m];

    	//문자 입력받기 
    	for (int i = 0; i < n; i++) {  
    		String str = br.readLine();
            for (int j = 0; j < m; j++) {    
                arr[i][j] =  str.charAt(j);    
            }
        }
    	
    	int cnt=0;
    	//전체 배열 돌면서 dfs로 탐색
    	for(int i=0; i<n; i++) {
    		for(int j=0; j<m; j++) {
    			 //방문하지 않은 노드라면 dfs수행 
    			if(!isVisited[i][j]) {
    				dfs(i,j);
    				cnt++;
    				
    			}
    				
    		}
    	}
    	 System.out.println(cnt); 
	}

	private static void dfs(int x, int y) {
		isVisited[x][y] = true;
		
		 // '-'인 경우, 오른쪽으로만 이동하면서 탐색
        if (arr[x][y] == '-') {
        	//오른쪽이 배열의 경계를 넘지 않고 && 그다음도 '-'이고 && 그다음도 방문하지 않았으면
            if (y + 1 < m && arr[x][y + 1] == '-' && !isVisited[x][y + 1]) {
                dfs(x, y + 1); //재귀호출하여 오른쪽으로 다시 이동하여 탐색
            }
        }
        
        // '|'인 경우, 아래쪽으로만 이동하면서 탐색
        if (arr[x][y] == '|') {
            if (x + 1 < n && arr[x + 1][y] == '|' && !isVisited[x + 1][y]) {
                dfs(x + 1, y);
            }
        }
		
	}
    
}