BFS DFS 선택 문의

정말 쉽게 풀어보는 코딩 테스트 top 기본 문제 (with 자바)

MaxOfIsland

21.03.01 16:28 작성

430

해당 문제의 input이 적을 경우에는 DFS로 풀어도 되는데, 엄청 큰 input 일 경우에는 BFS 로 풀어야 하는거 아닌가요?

해커랭커에 비슷한 유형의 문제를 DFS 로 하면 작은 input 에서는 통과가 되는거 같은데, 큰 input 에서는 콜스택 초과 에러가 나서 BFS 로 해결이 되네요.

콜스택을 쓰는게 의미있는 (문자열 순서를 맞춰서 찾는다던지)게 아니라 병렬형태로 카운팅 하는 부분은 그냥 BFS 를 쓴다고 생각하면 될까요?

https://www.hackerrank.com/contests/iit-guwahati-placement-preparation-test-02/challenges/largest-island

java 코테 준비 같이 해요!

답변 4

푸샵맨 코딩스터디

지식공유자

2021. 03. 02. 23:30

안녕하세요~

말씀해주신

1. DFS의 핵심은 function 들어가자마자 탈출 조건부터 기록 하는게 핵심인거 같네요.

=> 네 맞습니다. bfs/dfs 파고들면서 , 체크하고 , 탈출하고 입니다. 그 부분만 에러체크 잘 해주면 됩니다.

무한대로 응용이 가능하기 때문에 또한 사고력을 판단한다고 생각하는지 무조건 나옵니다.

2. javascript 로 해 봤을 때는 여전히 callstack error 가 발생하네요 (로컬에서 node.js 로 돌릴 때)

=>제가 js는 확실히 몰라서..

어쨋거나 요새 javascript 도 많이 보더라고요

조심해야 할것은 javascript를 지원 안하는 회사가 있습니다.(작은곳)

자바 , 파이썬은 코테에서 무조건 지원하고 , 과제는 백엔드는 스프링이 , 프론트는 vue.js 가 대세입니다.

자바, 파이썬은 거의 필수죠 이젠 ...잘 하시길 바랍니다.

수고하세요~

jihyeon.jang

질문자

2021. 03. 02. 19:48

댓글들 감사합니다.

DFS의 핵심은 function 들어가자마자 탈출 조건부터 기록 하는게 핵심인거 같네요.

저는 javascript 로 해 봤을 때는 여전히 callstack error 가 발생하네요 (로컬에서 node.js 로 돌릴 때)

java 와 js 의 call stack 이 다르긴 한가보네요.

푸샵맨 코딩스터디

지식공유자

2021. 03. 01. 21:01

단순히 방향만 8가지로 바꿔도 답이 나옵니다.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the maxRegion function below.
     int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1},{1,1},{1,-1},{-1,1},{-1,-1}};
     int m ,n;
     int maxRegion(int a, int b, int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        m = a;
        n = b;
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, 0);
                    System.out.println("area: " + area);
                    max = Math.max(area, max);
                }
            }
        }
        return max;

    }
    int  dfs(int[][] grid, int x, int y, int area) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
            return area;
        }
        grid[x][y] = 0;
        area++;
        for(int[] dir: dirs) {
            area= dfs(grid, x+dir[0], y+dir[1], area);
        }

        return area;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int m = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[][] grid = new int[m][n];

        for (int i = 0; i < m; i++) {
            String[] gridRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int j = 0; j <n; j++) {
                int gridItem = Integer.parseInt(gridRowItems[j]);
                grid[i][j] = gridItem;
            }
        }
        Solution a = new Solution();
        int res = a.maxRegion(m,n, grid);

        bufferedWriter.write(String.valueOf(res));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

푸샵맨 코딩스터디

지식공유자

2021. 03. 01. 19:53

안녕하세요~

위 문제는 direction 방향을 추가해줘야 합니다.

int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1},{1,1},{1,-1},{-1,1},{-1,-1}};

제가 강의에서 푼건 가장 기본적인 내용이고 , 위 문제는 응용부분이 있습니다.

방향을 4방향이 아니라 8방향입니다.

그리고 저는 콜스택 초과 에러가 안나는데요..

아마 제 강의 소스 그대로 돌리면 dfs에서 에러체크 하는 부분에 stackoverFlow가 발생할겁니다.

문제가 다 조금씩 변형되기 때문에 주의 깊게 보시면 될거 같네요.

1. 질문 주신 bfs/dfs 선택은 제가 볼때는 강의에서 강조했듯이

BFS/DFS의 차이는 너비우선순회, 깊이우선순회, Queue 이냐 Stack 이냐

bfs는 근접해 있는걸 찾아가는거죠

전 주로 bfs방식으로 풉니다.

dfs 깊이를 가져가면서 푸는데 양 방식 모두 해결할 수 있어야합니다.

제 강의 코딩테스트 전 알아야 개념에 공식으로 만들어 놨습니다.

2. 해커랭크는 아래처럼 풀면 답이 나옵니다.

1, 방향추가 8방향

2. visited[x][y] => 한번지나간 자리 이력관리 추가

int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } ,{1,1},{1,-1},{-1,1},{-1,-1}};

int m, n;

public int maxAreaOfIsland(int[][] grid) {

if (grid == null || grid.length == 0) {

return 0;

}

m = grid.length;

n = grid[0].length;

boolean[][] visited = new boolean[m][n];

int max = 0;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (grid[i][j] == 1 && !visited[i][j]) {

int area = dfs(grid, i, j, visited);

System.out.println("area: " + area);

max = Math.max(area, max);

}

return max;

}

int dfs(int[][] grid, int x, int y, boolean[][] visited) {

if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1 || visited[x][y]) {

return 0;

}

// grid[x][y] = 0;

visited[x][y] = true;

int area = 1;

for (int[] dir : dirs) {

area += dfs(grid, x + dir[0], y + dir[1], visited);

}

return area;

}

인프런 커뮤니티 질문&답변

BFS DFS 선택 문의