[Silver IV/JAVA] 1388 바닥장식

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

 

 

• '-' 이런 문자가 나오면 -> 이 방향으로 탐색, '|' 이런 문자가 나오면 ↓ 이 방향으로 탐색한다고 생각하면 된다.
• 여기서 어떤 경우에 인접리스트를 사용하고 어떤 경우에 2차원 배열을 사용하는지가 궁금해졌다.

* 인접 리스트 사용하는 경우
- 정점이 많고, 각 정점에 연결된 간선의 수가 적을 때
- 정점 중심의 탐색
- 입력이 정점-간선 목록으로 주어질 때

* 2차원 배열(그리드, 인접 행렬)을 사용하는 경우
- 정점 개수에 비해 간선 개수가 많을 때 ( 예 : N x N 행렬에서 모든 정점이 연결된 완전 그래프 )
- 그래프가 2D 격자 형태일 때 ( 예 : 미로찾기, 섬의 개수, 경로 탐색 등 )
- 정점 간 연결 여부 체크할 때 ( 예 : 경로 존재 확인 )

• 결론
  • 그래프의 크기와 연결 정보의 밀도 파악
  • 정점 수와 간선 수가 적고 탐색이 격자 형태라면? 2차원 배열
  • 정점 수가 많고 간선정보가 희소하다면? 인접리스트

• DFS (깊이우선탐색) 를 적용해서 풀이한다.
  • 오른쪽 방향으로 행을 따라서 탐색을 전개하다 '|' 문자를 만나면 아래 방향으로 열을 따라 탐색한다.
  • 2차원 배열로 방문여부와 문자열이 담긴 그리드를 만든다.
  • DFS 탐색 메서드에서 행과 열의 끝을 체크하기 위해 N,M 변수를 사용해야 하기 때문에 static 전역 변수로 선언한다.

 

풀이

import java.io.*;
import java.util.*;

public class Main{
    static boolean[][] visited;
    static char[][] graph;
    static int cnt;
    static int N,M;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        
        visited = new boolean[N+1][M+1];
        graph = new char[N+1][M+1];
        
        for(int i=1; i<N+1; i++){
            char[] c = br.readLine().toCharArray();
            for(int j=1; j<M+1; j++){
                graph[i][j] = c[j-1];
            }
        }
        
        //방문탐색
        for(int i=1; i<N+1; i++){
            for(int j=1; j<M+1; j++){
                if(!visited[i][j]){
                    dfs(i, j);
                }
            }
        }
        
        //출력
        System.out.println(cnt);
   
    }
    
    //DFS 탐색
    private static void dfs(int i, int j){
        visited[i][j] = true;
        
        if(graph[i][j]=='-'){ //->
            if(j==M){ //행의 끝이면
                cnt++;
                return;
            }
            int nextY = j+1;
            if(!visited[i][nextY] && graph[i][nextY] == '-'){ //방문한적 없고 '-'이면
                dfs(i, nextY); //재귀호출
            }else{
                cnt++;
                return;
            }
        }
        
        if(graph[i][j] == '|'){ //↓
            if(i==N){ //열의 끝이면
                cnt++;
                return;
            }
            
            int nextI = i+1;
            if(!visited[nextI][j] && graph[nextI][j] == '|'){ //방문한적 없으면서 '|'이면
                dfs(nextI, j); //재귀호출
            }else{
                cnt++;
                return;
            }
        }
    }
}