[99클럽 코테 스터디] 34일차 TIL - 양 한마리... 양 두마리...

오늘의 학습 키워드

</> 깊이/너비 우선 탐색(DFS/BFS)

공부한 내용 본인의 언어로 정리하기

//또 import안해줌
import java.util.*;

public class Main {
    static int H, W;
    static char[][] grid;
    static boolean[][] visited;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //테스트 케이스 개수 T
        int T = sc.nextInt();

        for (int t = 0; t < T; t++) {
            //높이 H, 너비 W인 grid 크기 제한
            H = sc.nextInt();
            W = sc.nextInt();
            grid = new char[H][W];
            visited = new boolean[H][W];

            //한줄씩 받아와서 그리드 생성
            for (int i = 0; i < H; i++) {
                String line = sc.next();
                grid[i] = line.toCharArray();
            }
            //양 그룹 count값 출력
            System.out.println(countSheepGroups());
        }
        sc.close();
    }
    
    static int countSheepGroups(){
        int count = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                //현재 위치가 양이고, 아직 방문하지 않았다면 dfs탐색
                if(grid[i][j] == '#' && !visited[i][j]){
                    dfs(i,j); //상하좌우 탐색을해서 인접한 '#'이 없을 때 까지 재귀적으로 반복탐색을 진행하고 끝나면 count를 올려줌
                    count++;
                }   
            }
        }
        return count;
    }
    //리턴이 없어야 돼서 void 추가
    static void dfs(int i, int j){
        //현재 위치가 그리드를 벗어났거나, 이미 방문했거나, 양이 아니라면 탐색 중단
        //결론적으로 범위 내에 있거나 방문하지않은 양일 경우 방문을 하고 저장을 한 다음 상하좌우 탐색한다.
        if(i < 0 || j < 0 || i >= H || j >= W || visited[i][j] || grid[i][j] != '#'){
            return;
        }
        visited[i][j] = true; //방문 완료 표시
        
        //상하좌우 재귀적으로 dfs 탐색 (오늘 문제는 대각선은 안보기때문에 경우의 수가 줄어들었음)
        dfs(i-1, j);//상
        dfs(i+1, j);//하
        dfs(i, j-1);//좌
        dfs(i, j+1);//우
        
    }
}

오늘의 회고

오늘 문제도 백준이어서 많이 어려울거라 생각했는데 점점 조금씩 이해가 가지 시작해서 오늘은 내 힘으로 풀기는 가능했던 문제였던것 같다.
백준이어서 컴파일 에러가 8번이나 났지만 완성한게 어딘가 싶다.

오늘 문제는 탐색을 통해서 #인 양의 그룹을 출력하는 문제였다.

오늘 탐색을 위해 나는 재귀를 이용하기 위해 일반적으로 많이 이용하는 DFS를 이용했다.

우선 사용할 변수들을 초기화 시켜주고 시작했다.

static int H, W;
static char[][] grid;
static boolean[][] visited;

그리고 메인에서는 변수 값들을 입력받고 출력해주는 과정을 만들었고 가독성과 안정성을 위해 모든 작업이 끝난 후에 Scanner를 닫아주었다.

 public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
	//테스트 케이스 개수 T
    int T = sc.nextInt();

	for (int t = 0; t < T; t++) {
		//높이 H, 너비 W인 grid 크기 제한
        H = sc.nextInt();
	    W = sc.nextInt();
	    grid = new char[H][W];
        visited = new boolean[H][W];

	    //한줄씩 받아와서 그리드 생성
		  for (int i = 0; i < H; i++) {
          String line = sc.next();
          grid[i] = line.toCharArray();
      }
     //양 그룹 count값 출력
       System.out.println(countSheepGroups());
    }
	sc.close();
}

양들의 그룹을 세어줄 countSheepGroups을 만들어 주었다.

static int countSheepGroups(){
	int count = 0;
    for (int i = 0; i < H; i++) {
    	for (int j = 0; j < W; j++) {
        	//현재 위치가 양이고, 아직 방문하지 않았다면 dfs탐색
        	if(grid[i][j] == '#' && !visited[i][j]){
            	//상하좌우 탐색을해서 인접한 '#'이 없을 때 까지 재귀적으로 반복탐색을 진행하고 끝나면 count를 올려줌
            	dfs(i,j); 
                count++;
	        }   
		}
    }
	return count;
}

이제 재귀를 위한 dfs 메서드를 만들어준다.

//리턴이 없어야 돼서 void 추가
    static void dfs(int i, int j){
        //현재 위치가 그리드를 벗어났거나, 이미 방문했거나, 양이 아니라면 탐색 중단
        //결론적으로 범위 내에 있거나 방문하지않은 양일 경우 방문을 하고 저장을 한 다음 상하좌우 탐색한다.
        if(i < 0 || j < 0 || i >= H || j >= W || visited[i][j] || grid[i][j] != '#'){
            return;
        }
        visited[i][j] = true; //방문 완료 표시
        
        //상하좌우 재귀적으로 dfs 탐색 (오늘 문제는 대각선은 안보기때문에 경우의 수가 줄어들었음)
        dfs(i-1, j);//상
        dfs(i+1, j);//하
        dfs(i, j-1);//좌
        dfs(i, j+1);//우
        
    }

만들면서 재귀에 대한 과정이 좀 와닿지않아서 햇갈렸지만 탐색을 하면서 원하는 값이 나올때까지 하는 것에 초점을 맞춰 인접하는 값이 없을때까지 탐색을 하고 방문처리를 해버리면 하나의 그룹이 만들어진다는 것을 확실히 이해를 했어서 크게 얻어가는게 있는 문제였던것 같다.

AI 코드리뷰

현재 코드의 장점

1. 명확한 구현:
   • countSheepGroups()와 dfs() 함수는 각각 양 그룹을 세고 탐색하는 기능을 잘 구현하고 있습니다.
   • 코드가 읽기 쉬우며, 각 함수의 역할이 명확하게 나뉘어 있습니다.
2. 재귀적 DFS:
   • 재귀를 이용하여 DFS를 구현함으로써 깊이 우선 탐색을 자연스럽게 수행하고 있습니다.
   • visited 배열을 사용하여 중복 방문을 방지하고, 탐색 범위를 제한하여 효율성을 높입니다.

현재 코드의 단점

1. 메모리 사용:
   • visited 배열과 grid 배열을 사용하여 추가 메모리를 소모합니다. 이 메모리 사용량은 𝑂(𝐻×𝑊) 입니다.
   • 깊이 우선 탐색의 경우, 재귀 호출로 인해 스택 메모리도 사용합니다. 그리드가 매우 클 경우, 스택 오버플로우가 발생할 수 있습니다.
2. 재귀 한계:
   • Java의 재귀 깊이는 기본적으로 제한이 있으므로, 매우 큰 그리드에서는 스택 오버플로우가 발생할 수 있습니다.

시간 복잡도

• 시간복잡도:
  • countSheepGroups()는 전체 그리드에 대해 두 개의 중첩 루프를 돌면서 탐색을 수행합니다. 이 루프의 시간복잡도는 𝑂(𝐻×𝑊)입니다.
  • dfs() 함수는 호출할 때마다 상하좌우로 재귀 호출을 하므로, 최악의 경우 모든 셀을 탐색하게 되어 시간복잡도는 𝑂(𝐻×𝑊)로 예상됩니다. 각 셀을 방문하는 데는 O(1) 시간이 걸리므로, 전체 시간복잡도는 여전히 𝑂(𝐻×𝑊)입니다.

개선된 코드 리뷰

재귀 대신 명시적인 스택을 사용하여 DFS를 구현할 수 있습니다. 이를 통해 스택 오버플로우 문제를 방지할 수 있습니다.

import java.util.*;

public class Main {
    static int H, W;
    static char[][] grid;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int t = 0; t < T; t++) {
            H = sc.nextInt();
            W = sc.nextInt();
            grid = new char[H][W];
            visited = new boolean[H][W];

            for (int i = 0; i < H; i++) {
                String line = sc.next();
                grid[i] = line.toCharArray();
            }
            System.out.println(countSheepGroups());
        }
        sc.close();
    }

    static int countSheepGroups() {
        int count = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (grid[i][j] == '#' && !visited[i][j]) {
                    iterativeDFS(i, j); // 스택을 사용한 DFS
                    count++;
                }
            }
        }
        return count;
    }

    static void iterativeDFS(int startI, int startJ) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{startI, startJ});

        while (!stack.isEmpty()) {
            int[] position = stack.pop();
            int i = position[0];
            int j = position[1];

            if (i < 0 || j < 0 || i >= H || j >= W || visited[i][j] || grid[i][j] != '#') {
                continue;
            }

            visited[i][j] = true;

            stack.push(new int[]{i - 1, j}); // 상
            stack.push(new int[]{i + 1, j}); // 하
            stack.push(new int[]{i, j - 1}); // 좌
            stack.push(new int[]{i, j + 1}); // 우
        }
    }
}

개선된 버전의 장점

1. 스택 오버플로우 방지:
   • 재귀 대신 명시적인 스택을 사용하여 DFS를 구현함으로써, 깊이 우선 탐색에서 발생할 수 있는 스택 오버플로우 문제를 해결합니다.
2. 메모리 관리:
   • 스택을 사용하는 DFS는 메모리 사용을 좀 더 제어할 수 있으며, 재귀 호출로 인한 호출 스택의 깊이 제한에 영향을 받지 않습니다.
3. 성능:
   • 성능 측면에서는 재귀적 DFS와 비슷한 성능을 유지하며, 시간복잡도는 여전히 𝑂(𝐻×𝑊)입니다.

개선된 버전의 단점

1. 코드 복잡도 증가:
   • 재귀 대신 스택을 사용하는 방법은 코드가 조금 더 복잡해지며, 스택의 사용과 관리를 명시적으로 해야 합니다.
2. 추가 메모리:
   • 명시적 스택을 사용하므로 스택을 위한 추가 메모리가 필요합니다. 하지만 이는 재귀 호출로 인한 스택 오버플로우를 방지하는 것이므로 장점이 될 수 있습니다.

시간 복잡도

• 시간복잡도는 여전히 𝑂(𝐻×𝑊)입니다.

---

내일 공부할 것 :

재귀와 반복적인 방법의 장단점을 비교해 보아야겠다.

문제

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