developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 운영체제인터럽트
  • 삼성코테준비
  • MA모형
  • 삼성코테자바풀이
  • 삼성코테파이썬풀이
  • SW역량테스트파이썬
  • 통계학
  • 카카오코테java풀이
  • SW역량테스트파이썬풀이
  • 통계분석
  • AR모형
  • ARIMA모형
  • 시계열
  • c++디자인패턴
  • 카카오코테
  • 삼성코테자바준비
  • 삼성코테기출
  • 백준파이썬풀이
  • 삼성코테자바꿀팁
  • BOJ파이썬풀이
  • 삼성코테구현풀이
  • 코테파이썬
  • Arima
  • 삼성코테구현문제추천
  • 삼성코테기출자바풀이
  • c++ 빌더 패턴
  • 시계열분석
  • 삼성코테파이썬준비
  • 데이터분석
  • 삼성코테파이썬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 거짓말 1043번 (JAVA)

2022. 12. 6. 23:46

❓ 문제 - 백준 거짓말 1043번 - JAVA 풀이법

출처

(https://www.acmicpc.net/problem/1043)

 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

 

 

 

📝 문제해결법

1. 문제

  • 지민이가 파티장에 가서 거짓을 얘기하거나 진실을 얘기하게 된다.
  • 그러나 어떤 사람들은 지민이가 거짓말을 얘기하는지 알게 된다. 그리고 그 지민이가 거짓말을 얘기하는지, 진실을 얘기하는지 아는 사람들과 같이 파티장에 있는 사람들도 이런 거짓말을 하게 되는지 알게된다.
  • 따라서 다른 파티장에서는 거짓말을 한 것을 모르지만, 다른 파티에서는 거짓말을 하는지 알고 있는 파티원과 같이 있으면 모순을 느끼며 거짓말 쟁이로 판단된다.
  • 이렇게 모순을 피해 지민이가 거짓말 쟁이가 안되며 최대한 거짓말을 할 수 있는 파티장의 갯수를 구하여라.   

 

2. 해결 방법

  • union find(합집합) 알고리즘을 사용하여 문제를 해결한다.
  • 우선, 진실인지 거짓인지 아는 파티원들을 boolean true로 관리하며, 각 파티장에 참석한 사람에 대한 정보를 HashSet으로 저장한다.
  • 그리고 각 파티장에 대한 정보를 받을 때 각 멤버들을 union find로 해서 같은 집합으로 만든다.
  • 그리고 다시 한번, 진실인지 거짓인지 아는 파티원을 기준으로 자신과 같은 집합인 경우인 사람들은 다 진실과 거짓을 판별할 수 있게 되므로 boolean을 true로 변경해준다.
  • 그리고 다시 한번, 각 파티장마다 혹시 진실을 아는 사람이 존재한다면 스킵하고 각 파티장에 진실을 아는 사람이 아무도 없을 때 answer 1증가시켜주고, answer를 답으로 출력한다.

 

 

3. 느낀점

  • 처음에 union find말고 boolean으로 체킹하면서 비슷하게 로직을 구현했는데, 예제 인풋 아웃풋은 맞았지만.. 틀렸다.. 알고 보니 union find의 합집합으로 진실을 아는 사람 + 진실을 알게 될 사람을 묶고  나중에 다시 한번 더 진실을 알게되는 사람들의 연관관계를 다시 계산해줘야했다.
  • union find가 이런 식으로 풀이에 적용될 수 있구나 느꼈다..!

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main_1043 {
    public static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        boolean[] know = new boolean[n+1];
        HashSet<Integer>[] party = new HashSet[m+1];
        parent = new int[n+1];
        for(int i=1;i<=m;i++){
            party[i] = new HashSet<>();
        }
        st = new StringTokenizer(br.readLine(), " ");
        int know_cnt = Integer.parseInt(st.nextToken());
        for(int i=1;i<=know_cnt;i++){
            int tmp = Integer.parseInt(st.nextToken());
            know[tmp] = true;
        }

        for(int i=1;i<=n;i++){
            parent[i] = i;
        }

        // 진실을 아는 사람과 같은 파티 공간에 있으면 진실을 아는 것으로 체크
        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int num = Integer.parseInt(st.nextToken());
            if(num <= 0) continue;
            int pre = Integer.parseInt(st.nextToken());
            party[i].add(pre);
            for(int j=0;j<num-1;j++){
                int p = Integer.parseInt(st.nextToken());
                if(find_parent(pre) != find_parent(p)){
                    union(pre, p);
                }

                party[i].add(p);
                pre = p;
            }
        }

        // 진실을 아는 사람과 연관관계가 있음
        boolean[] check = new boolean[n+1];
        for(int i=1;i<=n;i++){
            if(know[i] && !check[i]){
                int p = find_parent(i);
                for(int j=1;j<=n;j++){
                    if(find_parent(j) == p){
                        know[j] = true;
                        check[j] = true;
                    }
                }
            }
        }

        int answer = 0;
        for(int i=1;i<=m;i++){
            boolean c = false;
            for(int p:party[i]){
                if(know[p]){
                    c = true;
                    break;
                }
            }
            if(!c) answer++;
        }

        System.out.println(answer);
    }

    public static int find_parent(int x){
        if(parent[x] == x) return x;
        return parent[x] = find_parent(parent[x]);
    }

    public static void union(int a, int b){
        a = find_parent(a);
        b = find_parent(b);
        if(a <= b){
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }


}

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 단어 수학 1339번 (JAVA)  (0) 2023.01.12
BOJ - 수들의 합4 2015번 (JAVA)  (7) 2022.12.07
2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (JAVA)  (0) 2022.12.01
프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)  (0) 2022.11.29
프로그래머스 코딩테스트 연습 - 카펫 (JAVA)  (0) 2022.11.22
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 단어 수학 1339번 (JAVA)
    • BOJ - 수들의 합4 2015번 (JAVA)
    • 2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (JAVA)
    • 프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바