inflearn logo
강의

Khóa học

Chia sẻ kiến thức

[Java/Java] Thuật toán DFS mà ngay cả sinh viên giáo dục khai phóng cũng có thể hiểu được! - Giới thiệu

Vua Nhảy Jellie (Nhỏ) (Baekjun 16173)

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

Đã giải quyết

71

dnrwls9115

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

1

import java.util.*;
import java.io.*;

public class jelly {

    static int size;
    static int[][] map;
    static boolean[][] visited;
//    //size,size도달하면 HaruHaru, 아니면 hing

    public static void dfs(int y, int x){
        visited[y][x] = true;
        if(y == size && x == size) return;
        int n = map[y][x];
        if( (x + n) <= size && !visited[y][x+n])  dfs(y,x+n);
        if( (y + n) <= size && !visited[y+n][x])  dfs(y+n,x);
    }



    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        size = Integer.parseInt(br.readLine());
        int Max = size +10;

        map = new int[Max][Max];
        visited = new boolean[Max][Max];

        for(int i = 1; i <= size; i ++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= size; j ++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(1,1);

        if(visited[size][size]){
            System.out.print("HaruHaru");
        }else  System.out.print("Hing");

        bw.close();
        br.close();
    }
}

java 코딩-테스트 알고리즘 dfs

Câu trả lời 1

0

gaebaljob

네, 잘 작성하셨습니다. DFS 코드는 문제 없이 정상적으로 동작합니다.

 

차이점을 이미 잘 아시겠지만 정리하자면:

 

  • 제 코드(ver 1): 이동할 방향(dirY, dirX)을 배열로 정의하고, for문으로 상하좌우를 탐색합니다. 이 방식은 이동 가능한 방향이 많을 때 코드를 간결하게 작성할 수 있습니다.

  • 작성하신 코드: if문을 사용해 아래(y + n)와 오른쪽(x + n) 방향을 각각 따로 확인하고 있습니다. 이 방법도 문제에서는 동일하게 동작하고, 오히려 더 직관적으로 이해하기 쉽습니다.

 

 

두 방식 모두 visited 배열을 활용하기 때문에 논리적으로 완벽하며, 결과에도 차이는 없습니다.

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

1

94

2

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

1

62

2

graph 채울때 for문 설계 질문

1

71

2

질문있습니다.

1

71

1

다른 강의 언제나오나용?

1

92

2

노드간 거리 계산

1

145

1

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

1

130

1

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

1

143

1

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

0

133

2

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

1

115

1

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

1

249

3

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

1

201

2

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

1

224

1

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

1

325

3

촌수 계산

1

354

3

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

1

267

1

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

1

381

1

백준 실행시 틀립니다.

1

372

1

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

1

408

1

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

1

370

1

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

2

313

1

출력할 때 BufferedWriter? StringBuilder?

1

508

1

answer++ 위치 질문

1

254

1

code의 어디가 잘못된지 도저히 모르겠습니다..

1

269

1