DFS 관련 문제 모음!

WOOK JONG KIM·2023년 4월 4일

코딩테스트_문제모음집

코테문제_모음집

목록 보기

6/12

특징

안 이어져 있는 정점은 DFS로 방문할 수 없을까? -> O

그래프의 용어 중 연결 요소(컴포넌트)라는게 있다
-> 컴포넌트 하나 안에 속한 정점은 모두 이어져 있으며, 다른 컴포넌트 끼리는 이어져 있지 않음

DFS를 한번 하면 다 끝나더라도 시작점이 속한 컴포넌트의 정점들만 방문하고, 나머지는 방문 불가
-> 즉 모든 정점을 방문하려면 각 컴포넌트에 속한 정점들 중 하나씩은 방문 시도를 해 줘야 하고, 이를 구현하는 쉬운 방법은 반복문을 돌면서 방문하지 않은 정점을 볼때마다 DFS를 시작해 주는 것
-> 이때 방문을 시도하는 횟수가 컴포넌트의 갯수가 됨

DFS의 시간복잡도 O(V+E) : 노드의 간선 수의 합
-> 한번 방문한 정점은 다시 방문하지 않으며, 한 정점에서 다음으로 방문할 노드들을 순회하는 횟수가 그 정점의 차수와 같음
-> 만약 인접 리스트가 아닌 인접 행렬의 경우에는, 다음에 방문할 정점을 찾을 때 모든 정점을 순회하며 둘이 이어져 있는지 체크해야 하므로 O(V^2)이 됨

문제 1(유기농 배추) - 실버2

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

이 경우엔 인집 리스트가 별로 필요 없음
-> 각 정점마다 인접한 정점이 4개뿐
-> 칸마다 대응하는 2차원 visited 배열만 따로 만들어도 해결 가능

문제 2(음식물 피하기) - 실버1

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

처음 푼 코드

public class Main {
    static int M,N;
    static int[][] canMove;
    static int[][] road;
    static int maxSize;
    static boolean visited[][];
    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());
        int K = Integer.parseInt(st.nextToken());
        canMove = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        road = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            road[x][y] = 1;
        }
        maxSize = 0;

        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                dfs(i,j,1);
            }
        }
        System.out.println(maxSize);
    }
    public static void dfs(int x, int y, int depth){
        if(x < 1 || x > N || y < 1 || y > M || road[x][y] == 0 || visited[x][y]){
            return;
        }

        maxSize = Math.max(maxSize,depth);
        visited[x][y] = true;

        for(int[] move : canMove){
            int tempX =  x+move[0]; int tempY = y+move[1];
            dfs(tempX,tempY,depth+1);
        }
        visited[x][y] = false;
    }
}

시간초과 발생..
-> visited를 계속 초기화하였고, 모든 경우에 따라 dfs를 진행하였음

정답 코드

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

public class Main {
    static int M,N;
    static int[][] canMove;
    static int[][] road;
    static int maxSize = 0;
    static boolean visited[][];
    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());
        int K = Integer.parseInt(st.nextToken());
        canMove = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        road = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            road[x-1][y-1] = 1;
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
               if(road[i][j] == 1 && !visited[i][j]){
                   maxSize = Math.max(maxSize, dfs(i,j));
               }
            }
        }
        System.out.println(maxSize);
    }
    public static int dfs(int x, int y){
        visited[x][y] = true;
        int count = 1;

        for(int[] move : canMove){
            int tempX = x + move[0];
            int tempY = y + move[1];

            if(tempX >= 0 && tempX < N && tempY >= 0 && tempY < M && road[tempX][tempY] == 1 && !visited[tempX][tempY]){
                count += dfs(tempX, tempY);
            }
        }
        return count;
    }
}