inflearn logo
강의

Khóa học

Chia sẻ kiến thức

Các vấn đề kiểm tra mã hóa cơ bản hàng đầu được giải quyết thực sự dễ dàng (với Java)

MaxOfIsland

BFS DFS 선택 문의

560

jihyeonjang9662

5 câu hỏi đã được viết

1

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

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

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

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

java 코테 준비 같이 해요!

Câu trả lời 4

0

pushupman

안녕하세요~

말씀해주신

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

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

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

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

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

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

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

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

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

수고하세요~

0

jihyeonjang9662

댓글들 감사합니다.

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

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

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

0

pushupman

단순히 방향만 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

pushupman

안녕하세요~

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

강의자료에 나오는 m과 n의 범위가 코딩하고 다른거 같습니다

0

298

0

나선형매트릭스 깃허브에 코드가 없는것같아요

0

247

0

로그 파일의 데이터 재정렬 코드가 깃허브에 없어요!

0

266

0

새로 생긴 기초강의 질문드려요

1

438

1

질문드립니다

1

292

1

Unique Paths Integer 질문입니다

0

268

1

subString 방법으로 문제 풀이 영상은 짤린건가요?

1

311

1

DFS 방식으로 푼 것이 맞나요?

0

373

2

질문드립니다~

0

238

1

left if문에 대해서

1

301

1

오타 인가요?

1

285

1

안녕하세요 강사님

1

225

1

질문 드립니다

0

230

2

Queue&Stack 문제해설집 문의

0

213

1

문제분석 로직 질문

1

270

1

시간 복잡도 문의드립니다.

1

276

1

시간복잡도 질문드립니다.

1

244

1

for-each 문 질문있습니다!

0

342

1

강의영상에서 사용된 로그 메소드가 궁금합니다.

2

350

2

강의자료 + 문제 이해 관련 질문입니다

1

346

3

강사님 오류맞나요?

1

239

1

강사님 시간 복잡도에 대해서 질문드립니다.

1

222

1

질문입니다.

1

251

1

문제에 대한 이해

1

353

1