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

안녕하세요 유진님. 답변드리겠습니다.

1. 와 맞네요.. 이건 제가 실수한게 맞습니다. 결론만 말씀드리면 예시 2가 문제에서 제시한 대칭적(양방향)규칙을 따른거고, 예시 1은 [[1, 2], [0, 2], [0, 1]] (보충설명하자면 [0: [1, 2], 1: [0, 2], 2: [0, 1]]) 이렇게 변경되어야 되겠네요. 짚어주셔서 감사합니다.

2. 양방향그래프 == 무방향그래프 같다고 보시면 됩니다. 이 문제는 양방향(무방향)그래프를 노리고만든 문제입니다.

3. 입력값이 어떤 형태인지 이해를 해야되는데, 문제에서 보면
friends[i]는 i번째 학생과 친구인 학생들의 번호를 나타냈다고 했잖아요. 이게 즉 i번째 인덱스에는 i번 노드랑 연결되어있는 노드들을 나열해놓겠다 == 인접리스트에 대한 설명.

그래서 friends는 그 자체로 인접리스트가 됩니다.
이전 문제는 보통 간선리스트 형태의 입력값이였을 겁니다. 간선리스트는 문제에서 이렇게 표현될거에요.
"친구 관계를 나타내는 m개의 간선 정보가 주어집니다."

인접리스트일때는
예시 2번 friends = [[1, 2], [0, 3], [0], [1]]

간선리스트라면?
n = 4 (학생 수)
edges = [[0, 1], [0, 2], [1, 3]]

4. 강의영상에서 dfs(재귀)를 사용한 풀이를 보여드렸는데, BFS(queue 사용한 구조)를 사용하셔도 됩니다. 잘 하신겁니다. 한번 작성해서 답글에 남겨서 저도 보여주시겠어요?


이해에 도움이 되었을까요!? 궁금한거 있으면 편하게 질문 주세요~!

빠른 답변 감사합니다 덕분에 이해 되었어요!

아래는 dfs로 구현한 코드입니다. ide에서 테스트 케이스 결과는 맞게 나오는데 문제사이트에서 돌리니 시간초과가 나더라구요. 혹시 원인을 확인해주실 수 있을까요?🥲

public boolean solution(int[][] friends) {
    int[] visited = new int[friends.length];
    Arrays.fill(visited, -1);

    for(int i=0; i<friends.length; i++) {
        if(visited[i] == -1) {
            if(!bfsFail2(i,friends,visited)) {
                return false;
            }
        }
    }

    return true;
}

    public boolean bfs(int start, int[][] friends, int[] visited) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
        visited[start] = 1;

        while(!q.isEmpty()) {
            int cur = q.poll();

            for(int nxt : friends[cur]) {
                int nxtTeam = visited[cur] == 0 ? 1 : 0; // nxt의 팀 배정
                if(visited[nxt] < 0) { // 아직 미방문
                    q.offer(nxt);
                    visited[nxt] = nxtTeam;
                }else if(visited[nxt] != nxtTeam) { // 이미 방문했는데 팀 배정 불일치 (false)
                    return false;
                }
            }
        }
        return true;
    }