inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편

바닥 장식 (백준 1388)

dfs를 호출 할 때 매개변수..?

해결된 질문

256

oilater

작성한 질문수 11

2

안녕하세요! 강의 넘 잘 듣고 있습니다. 하루만에 거의 다들었네요,,ㅋㅋ

질문이 있습니다

혹시 dfs를 호출할 때 이런 '-'나 '|' 같은게 나오면

매개변수로 '-' 나 '|' 를 추가해서 dfs함수에 넘겨도 되는건가요?

저는 이렇게 할 때가 많은데

이렇게 하지 않고 오히려 dfs 함수 안에서 해결해주는 게 더 간단한 것 같기도 해서요..

 

보통은 어떻게 하시나요?

 

전 4방 탐색을 하면서 이렇게 풀었었네요,, 한 방향만 탐색하는 팁 배워갑니다 ㅎㅎ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static int N, M;
    static char[][] arr;
    static int ans;
    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());
        arr = new char[N+2][M+2];

        for (int i = 1; i <= N; i++) {
            String str = br.readLine();
            for (int j = 1; j <= M; j++) {
                arr[i][j] = str.charAt(j-1);
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (arr[i][j] == '|') {
                    dfs(i, j, '|');
                    ans++;
                } else if (arr[i][j] == '-'){
                    dfs(i, j, '-');
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }

    private static void dfs(int r, int c, char shape) {

        int start = 0;
        int end = 0;

        if (shape == '|') {
            start = 0;
            end = 1;
        } else if (shape == '-'){
            start = 2;
            end = 3;
        }

        arr[r][c] = '1';

        for (int d = start; d <= end; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(arr[nr][nc] == shape) {
                arr[nr][nc] = '1';
                dfs(nr, nc, shape);
            }
        }
    }
}

 

java 코딩-테스트 알고리즘 매개변수

답변 1

2

개발자로 취직하기

oilater님 안녕하세요 :)

 

두 방법 다 좋다고 생각해요. oilater님이 말씀하신대로 현재 위치의 값을 매개변수로 전달하면 코드가 조금 더 깔끔해지고 가독성이 좋아지는 반면, 매개변수를 전달하는 만큼 아주 약간의 성능 저하가 있을 것 같아요.

반면 y,x 인덱스 값만 전달하면 어차피 내부에서 map을 바로 조회할 수 있으니 동작은 동일하게 구현 가능한데, 매번 map[y][x] 이런식으로 작성해야되서 코드가 길어진다는 단점이 있고 그만큼 매개변수는 없으니 성능이 아주 조금 빨라진다는 장점이 있는 것 같아요.

 

저는 개인적으로 후자를 선호합니다! 성능 차이가 크진 않아서 성능 때문은 아니고, 어차피 현재 위치의 값은 y,x 좌표만 있으면 조회할 수 있으니 굳이 그 값을 매개변수로 또 전달하는 게 오히려 헷갈려서 그래요. '이거 그냥 map에서 읽으면 되는데 왜 매개변수로 전달하지? 얘는 map의 값과 뭐가 다른 의미가 있는 건가?'라는 식의 의문이 들때가 있어서 전 map을 직접 접근하는 게 더 직관적이었던 것 같아요!

 

이건 순전히 선호도의 차이이고, 약간의 성능 개선은 있지만 이걸 제가 작성한 것처럼 한다고 해서 시간초과 날 답안이 정답이 되거내, oilater님이 제안한 방식으로 작성한다고 정답이 시간초과가 나지 않으니 원하시는 대로 쓰셔도 무방할 것 같아요! :D

 

주말에도 공부하시느라 고생 많으세요! 화이팅하시고 또 궁금하신 점은 언제든 물어봐주세요 :)

1

oilater

아아,, 그렇군요 ㅎㅎㅎ

저도 오히려 매개변수로 안넘기고 dfs 안에서 처리해서 푸는게 더 깔끔한 것 같아요 ㅋㅋ

앞으론 그렇게 해봐야겠네요

 

답변 너무 감사드립니다!!

남은 주말 잘보내세여! ㅎㅎ
강의 마니마니 찍어주세요 ㅠ ㅋㅋㅋ

 

dfs 부문을 이렇게 작성해도 되나요?

1

75

1

x랑 y를 거꾸로 쓰는 개념이 너무 헷갈립니다...

1

98

2

dfs 파라미터에 count를 넣는이유

1

66

2

graph 채울때 for문 설계 질문

1

75

2

질문있습니다.

1

76

1

다른 강의 언제나오나용?

1

95

2

노드간 거리 계산

1

148

1

안녕하세요, 혹시 다른문제도 여쭤볼 수 있을까요?

1

132

1

최근에 올린 질문, 코드블럭으로 공유드립니다!

1

144

1

질문이 있습니다. dfs 메서드에 order를 이렇게 구현하면 안되는 이유가 무엇인가요?

0

136

2

깊이우선탐색2 백준 24480 수업노트에...

1

122

1

백준 24479 문제 제출 결과 "틀렸습니다" 라고만 나와서 어떤 부분이 틀렸는지 잘 모르겠어요 피드백 부탁드립니다

1

252

3

graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?

1

202

2

graph를 2차원 배열 또는 List로 하는 기준을 어떤식으로 잡으면 좋을까요...?

1

225

1

강사님 안녕하세요! 깊이 우선 탐색 2 (백준 24480)에서 제공하는 풀이 코드에서 궁금한 점이 있어서 질문 드립니다!

1

329

3

촌수 계산

1

356

3

연결 요소의 개수 (백준 11724)

1

269

1

백준 24479 문제 시간 초과 질문 드려요

1

385

1

백준 실행시 틀립니다.

1

376

1

재귀대신 스택으로 구현하면 안될까요?

1

412

1

dfs 매개변수에서 y,x 를 왜 순서를 반대로 쓰셨는지 궁금합니다.

1

374

1

안녕하세요 11724번 질문드려요!

2

316

1

출력할 때 BufferedWriter? StringBuilder?

1

514

1

answer++ 위치 질문

1

258

1