인프런 커뮤니티 질문&답변

락곤님의 프로필 이미지
락곤

작성한 질문수

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

침투 (백준 13565)

침투 (백준 13565) 문제중 질문입니당

해결된 질문

작성

·

235

1

아래 코드에서 왜
DFS를 수행할때 MAP[1] 이 왜 고정인지 잘모르겠습니다...

 

//맵정보 저장
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) == '0' ? true : false);
    }
}

//dfs
for (int j = 1; j <= M; j++) {
    if (map[1][j]) {          // 왜 map[1][j] 일까요
        dfs(1, j);           //  또한 dfs도왜 1,j 일가요
    }
}

답변 1

1

안녕하세요 락곤님 :)

1로 고정되는 이유는 첫번째 값이 행을 의미하는 값이고, 문제에서 요구하기로 "1번 행에 있는 점 중 하나에서 출발해서 마지막 행에 도달할 수 있냐" 였기 때문입니다.

그래서 1번 행에서 침투가능한 모든 점에서 dfs를 태워보고, 이중 하나라도 마지막 행에 도달할 수 있으면 침투가 가능하다고 판단하는 것이 문제에서 기대한 동작이라서, 1번 행은 고정시켜놓고, 1번의 모든 열에서 침투 가능한 위치에서 침투를 시켜본다라고 이해하시면 될것 같아요!

위 내용 보시고도 불명확한 부분 있으몀 추가 댓글 남겨주세요!

락곤님의 프로필 이미지
락곤

작성한 질문수

질문하기