본문으로 건너뛰기

1765 - 닭싸움 팀 정하기

정보

풀이 키워드​

스포주의

그래프 유니온파인드


풀이 코드​

정보
  • 메모리: 21416 KB
  • 시간: 252 ms
import java.util.*;
import java.io.*;

public class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, m;
    static int[][] rel;
    static boolean[] visited;
    
    static void connect(int x) {
        // x 학생과 친구인 애들을 모두 visited 처리
        for (int i = 1; i <= n; ++i) {
            if (rel[x][i] == 1 && !visited[i]) {
                visited[i] = true;
                connect(i);
            }
        }
        
        // x 학생의 '원수의 원수'도 모두 visited 처리
        for (int i = 0; i <= n; ++i) {
            if (rel[x][i] == -1) {
                for (int j = 1; j <= n; ++j) {
                    if (rel[i][j] == -1 && !visited[j]) {
                        visited[j] = true;
                        connect(j); // 원수의 원수의 친구 & 원수의 원수의 원수의 원수도 찾기
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        rel = new int[n+1][n+1];
        visited = new boolean[n+1];
        
        for (int i = 0; i < m; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String data = st.nextToken();
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if (data.equals("F")) { // 친구 관계
                rel[a][b] = rel[b][a] = 1; // 칭구
            }
            else { // 원수 관계
                rel[a][b] = rel[b][a] = -1; // 남보다~ 못한~ 사이
            }
        }
        
        // 친구끼리만 그룹핑하고 나머지는 싱글로 두면 최대 개수의 팀이 생성됨
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                connect(i);
                ans += 1;
            }
        }
        
        System.out.println(ans);
    }
}

풀이 해설​

서로 연결연결된 친구 관계를 모두 찾기 위해 재귀를 이용했다.

친구 관계이면 강제로 한 팀이 되어야 하므로,
친구가 없는(...) 학생은 무조건 싱글플레이를 시켜야 가장 많은 팀 개수를 확보할 수 있다.

유니온파인드가 생각났긴 한데 또 로직 기억안나서 무지성 재귀 때림.


🤨 visited 저래 해도 됨?​

visited 처리 위치는 connect 함수 호출 전이 아닌, connect 함수 내의 최상단에 놓아도 되긴 한데,
DP 풀이를 고려해서 현 방식대로 작성했다. (DP 로직에선 visited 처리를 함수 호출 전후에 명시하는 것이 가독성에 좋음)

두 방식 모두 AC 여부에는 영향을 주지 않는다.


자바에 한글자 내용 비교 메소드 없음

자바는 Strongly Typed 언어이다.

data.equals("F")가 아닌 data.equals('F')와 같이 인자에 String이 아닌 char을 넣었을 경우
char이 Character로 autoboxing 되고, equals 내부의 이러한 로직에 의해

equals 내부 구현
public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    return (anObject instanceof String aString)
            && (!COMPACT_STRINGS || this.coder == aString.coder)
            && StringLatin1.equals(value, aString.value);
}

"F"에 대한 data.equals('F')의 결과는 false가 된다.


메모​

  • 이왜 ????????????????????
  • onlinegdb에서 풀면 tab 인덴트가 환경마다 자꾸 깨짐 돌아버리것네 mycompiler 써야할듯