inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

바닥 장식 (백준 1388)

바닥 장식 (백준 1388) 문제 질문입니당

해결된 질문

240

락곤

작성한 질문수 13

1

저는 맵2차원배열을 boolean으로 사용하고싶어
아래와 같이 코드를 작성해봤습니당... 예제입력1. 은 답이 잘나오는데 나머지는 왜 틀리게 나올까용...

 

package DFS;


import java.io.*;
import java.util.StringTokenizer;
import java.util.Vector;

/*
바닥 장식

https://www.acmicpc.net/problem/1388
 */
public class B1388 {
    final  static  int MAX =50+10;
    static  boolean [][] map;
    static  boolean [][] visited;
    static  int M,N;


    static  void  dfs(int y, int x){
        visited[y][x]=true;
        if (map[y][x]==true&& map[y][x+1]==true){
            dfs(y, x + 1);
        }
        if(map[y][x]==false&&map[y+1][x]==false){
            dfs(y+1,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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new boolean[MAX][MAX];
        visited = new boolean[MAX][MAX];

        //맵정보 반영
        for (int i = 1; i <= N; i++) {
            String str = br.readLine();
            for (int j = 1; j <= M; j++) {
                map[i][j] = (str.charAt(j - 1) == '-' ? true : false);
            }
        }

        //dfs
        int answer=0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if(map[i][j]&&visited[i][j]==false){
                    dfs(i,j);
                    answer++;
                }
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();

    }


}

 

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

답변 1

1

개발자로 취직하기

락곤님 안녕하세요 :)

main 함수 내에서 dfs를 호출하는 조건에 map[i][j]가 포함돼서 그런 것으로 보이네요!

작성하신 코그에서 map의 true/false는 가로/세로를 의미하기 때문에 true일때만 호출되고 false일때는 호출하지 않으면 제대로 정답이 안나올 것으로 보여요.

1번 예시는 가로 줄 4개만 있기 때문에 정답으로 나올 것 같고요!

 

1

락곤

답변 빠른답변 정말 감사합니다 !!!

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

1

74

1

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

1

97

2

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

1

65

2

graph 채울때 for문 설계 질문

1

73

2

질문있습니다.

1

75

1

다른 강의 언제나오나용?

1

94

2

노드간 거리 계산

1

146

1

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

1

131

1

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

1

143

1

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

0

135

2

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

1

120

1

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

1

251

3

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

1

202

2

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

1

224

1

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

1

328

3

촌수 계산

1

355

3

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

1

268

1

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

1

384

1

백준 실행시 틀립니다.

1

373

1

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

1

410

1

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

1

373

1

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

2

316

1

출력할 때 BufferedWriter? StringBuilder?

1

513

1

answer++ 위치 질문

1

257

1