알고리즘 코딩테스트 문제풀이 강의 - 48 이분 그래프 판별하기 (백준 1707)

[@codingtest]

강의 내용 중 실제 코딩하기 설명에서 코드의 38번째 라인을 'DFS(1)'에서 'DFS(i)'로 수정하는 것이 맞습니다.
참고 부탁드립니다. :)

[@김채윤-p7x]

크 설명 너무 잘하십니다👍👍👍

[@leezsche]

질문입니다.
죄송한데 이게 왜 무방향 그래프인가요?
이 문제에서 어떤 요소 때문에 이것을 방향그래프가 아닌 무방향그래프라고 단정지을 수 있는 건지 알려주세요.

[@codingtest]

안녕하세요 leezsche님 반갑습니다.
무방향 그래프라고 단정을 지었다기 보다는 해당 문제는 에지 방향이 있는지 판별 자체가 불필요하다는 느낌이 들었습니다.
제 생각이 틀릴 수도 있는데 방향 그래프인가? 무방향 그래프인가? 라는 생각이 들지 않았던 이유는
1. 문제에서 에지의 입력에 대해서 이야기할 때 입력 값에 따라 순서가 있다고 언급해 주지 않았기 때문에 방향을 알 수 없고,
2. 문제를 풀 때 (이분 그래프를 판별할 때) 에지의 방향을 알아야 할 필요성이 없기 때문이었습니다.
따라서 문제를 풀이 할 때 실제로 방향에 대해서 크게 생각하지 않고 풀이를 하였습니다.
생각이 모두 다르기 때문에 다른 방식으로 풀이가 가능할 수도 있을 것 같습니다.
질문 주셔서 감사합니다:)
즐거운 주말 되세요 ^^

[@leezsche]

@@codingtest 답변 감사드립니다. 좋은 책으로 잘 공부하고있어요^^
하루코딩님도 행복한 하루 되시길 바래요!

[@NabiInjeolmi]

// 안녕하세요. 강의듣고 백준에 문제를 한번 테스트를해봤는데 자꾸 틀리다고 하는데 어디부분이잘못된걸까요?
// ide에선 잘돌아가는데 백준에선 틀리다고나오네여.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main { // 이분그래프
// 그래프 데이터 저장 인접리스트
static ArrayList[] A;
static boolean[] visited;
static int[] check;
static boolean isEven;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다.
int testCase = Integer.parseInt(br.readLine());
for( int t=0; t

[@codingtest]

나비인절미님 안녕하세요!
탐색되지 않은 모든 노드에서 DFS를 수행하여야 하는 부분에서 아마 오타가 있는것 같습니다. ^^
if(isEven) {
DFS(1);
부분이 아래와 같이만 변경되면 성공이 됩니다. (1 -> i 로 변경)
if(isEven) {
DFS(i);
즐거운 주말 되세요 :)

[@NabiInjeolmi]

@@codingtest 감사합니다!! 아직코드이해 미숙한점이있긴한데 좀더 고민해보고 다시여쭤보겠습니다.!!! 선생님 좋은주말보내세요

[@石川優太-n9r]

유료급이네