• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

BFS DFS 선택 문의

21.03.01 16:28 작성 조회수 325

1

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

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

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

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

course-thumbnail

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

MaxOfIsland

강의실 바로가기

답변 4

·

답변을 작성해보세요.

0

푸샵맨 코딩스터디님의 프로필

푸샵맨 코딩스터디

지식공유자

2021.03.02

안녕하세요~

말씀해주신

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

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

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

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

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

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

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

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

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

수고하세요~

0

jihyeon.jang님의 프로필

jihyeon.jang

질문자

2021.03.02

댓글들 감사합니다.

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

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

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

0

푸샵맨 코딩스터디님의 프로필

푸샵맨 코딩스터디

지식공유자

2021.03.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();
    }
}

0

푸샵맨 코딩스터디님의 프로필

푸샵맨 코딩스터디

지식공유자

2021.03.01

안녕하세요~

위 문제는 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;
}

이 글과 비슷한 Q&A