[백준][Gold IV] Java - 1043번 : 거짓말

2025. 1. 28. 21:11·Java & Spring/코딩테스트

□ 문제 : 최대 거짓말 가능 회수를 카운트하는 프로그램 구현

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

  • 진실을 아는 사람이 없는 경우 파티 수 만큼 거짓말 가능
  • 진실을 아는 사람이 있는 경우 전염되어 거짓말을 할 수 있는 파티 수가 줄어듬
    ex)
    진실을 아는사람 (1)이 있다고 가정
    4번 파티에 진실을 아는사람(1)과 모르는 사람(2)가이 있고
    3번 파티에 (2)와 다른 모르는 사람(3)이 있다면 지민이는 3번 파티에서도 거짓말을 할 수 없게됨

□ 사용 알고리즘

  • BFS

□ 전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int N, M, P;
    static HashMap<Integer, Integer> trueP;
    static List<int[]> partyList = new ArrayList<>();
    static int[] party;
    static int count = 0;
    static boolean[] visit;
    static Queue<int[]> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {

        // 변수들 입력 받기
        input();

        // 진실을 아는 사람이 없는 경우 파티 수 만큼 리턴
        if (P == 0) {
            bw.write(Integer.toString(M));
            bw.flush();
            return;
        }

        // 파티 생성
        for (int i = 0; i < M; i++) {
            party(i);
        }

        // 진실을 아는 사람 겹치는 파티 체크
        BFS();

        // 파티를 순회하며 처리
        for (int[] party : partyList) {
            search(party);
        }

        bw.write(Integer.toString(count));
        bw.flush();
    }

    static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new boolean[M];

        st = new StringTokenizer(br.readLine());
        P = Integer.parseInt(st.nextToken());
        if (P != 0) {
            trueP = new HashMap<>();
            for (int i = 0; i < P; i++) {
                trueP.put(Integer.parseInt(st.nextToken()), 0);
            }
        }
    }

    static void party(int index) throws IOException {
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        party = new int[p];
        boolean flag = false;

        for (int i = 0; i < p; i++) {
            party[i] = Integer.parseInt(st.nextToken());
            if (trueP.containsKey(party[i])) {
                flag = true;
            }
        }

        if (flag) {
            q.add(party);
            visit[index] = true;
        }

        partyList.add(party);
    }

    static void BFS() {
        while (!q.isEmpty()) {
            int[] nowParty = q.poll();
            for (int i : nowParty) {
                if (!trueP.containsKey(i)) trueP.put(i, 0);
            }

            for (int i = 0; i < partyList.size(); i++) {
                if (!visit[i]) {
                    int[] nextParty = partyList.get(i);
                    for (int p : nextParty) {
                        if (trueP.containsKey(p)) {
                            q.add(nextParty);
                            visit[i] = true;
                        }
                    }
                }
            }
        }
    }

    static void search(int[] party) {
        for (int i : party) {
            if (trueP.containsKey(i)) return;
        }

        count++;
    }
}

 

□ 풀이 과정

0. main 함수

public static void main(String[] args) throws IOException {

        // 변수들 입력 받기
        input();

        // 진실을 아는 사람이 없는 경우 파티 수 만큼 리턴
        if (P == 0) {
            bw.write(Integer.toString(M));
            bw.flush();
            return;
        }

        // 파티 생성
        for (int i = 0; i < M; i++) {
            party(i);
        }

        // 진실을 아는 사람 겹치는 파티 체크
        BFS();

        // 파티를 순회하며 처리
        for (int[] party : partyList) {
            search(party);
        }

        bw.write(Integer.toString(count));
        bw.flush();
    }

 

1. 변수 값 입력 받기 - input()

static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new boolean[M];

        st = new StringTokenizer(br.readLine());
        P = Integer.parseInt(st.nextToken());
        if (P != 0) {
            trueP = new HashMap<>();
            for (int i = 0; i < P; i++) {
                trueP.put(Integer.parseInt(st.nextToken()), 0);
            }
        }
    }

 

2. 입력받은 변수에서 진실을 아는사람(P) 가 0인 경우 파티 수(M)만큼 결과 반환 프로그램 종료

  if (P == 0) {
            bw.write(Integer.toString(M));
            bw.flush();
            return;
        }

 

3. party 생성 - party(int index)

static void party(int index) throws IOException {
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        party = new int[p];
        boolean flag = false;

        for (int i = 0; i < p; i++) {
            party[i] = Integer.parseInt(st.nextToken());
            if (trueP.containsKey(party[i])) {
                flag = true;
            }
        }

        if (flag) {
            q.add(party);
            visit[index] = true;
        }

        partyList.add(party);
    }
  • main함수에서 party()함수를 호출 할 때 for문을 통해 index를 함께 전달
  • 만약 party안에 진실을 아는 사람이 있는 경우 큐에 추가 및 전달받은 index로 방문처리
  • 생성된 party는 list에 추가해줌(list의 index를 활용)

4. 진실을 아는 사람의 겹침을 확인하여 추가하는 함수 - BFS()

static void BFS() {
        while (!q.isEmpty()) {
            int[] nowParty = q.poll();
            for (int i : nowParty) if (!trueP.containsKey(i)) trueP.put(i, 0);

            for (int i = 0; i < partyList.size(); i++) {
                if (!visit[i]) {
                    int[] nextParty = partyList.get(i);
                    for (int p : nextParty) {
                        if (trueP.containsKey(p)) {
                            q.add(nextParty);
                            visit[i] = true;
                        }
                    }
                }
            }
        }
    }
  • 파티 생성 시 추가 큐에 추가된 배열부터 시작하여 partyList를 순회하며 겹치는 파티 모두 확인

5. 모든 파티를 순회 하며 진실을 아는 사람이 포함되지 않은 파티에 대해서 count를 증가

    static void search(int[] party) {
        for (int i : party) {
            if (trueP.containsKey(i)) return;
        }

        count++;
    }

 

 

 

 

 

'Java & Spring > 코딩테스트' 카테고리의 다른 글

[백준] Java - 1929번 : 소수 구하기  (0) 2024.12.10
[백준] Java - 1018번 : 체스판 다시 칠하기  (1) 2024.11.29
52일차 - 알고리즘 코드카타(실패)  (2) 2024.10.01
43일차 - 알고리즘 코드카타  (1) 2024.09.12
42일차 - 알고리즘 코드카타  (2) 2024.09.11
'Java & Spring/코딩테스트' 카테고리의 다른 글
  • [백준] Java - 1929번 : 소수 구하기
  • [백준] Java - 1018번 : 체스판 다시 칠하기
  • 52일차 - 알고리즘 코드카타(실패)
  • 43일차 - 알고리즘 코드카타
DJ.Kang
DJ.Kang
백엔드 개발 기록 블로그
  • DJ.Kang
    DJ Hello World
    DJ.Kang
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 이론공부
        • 개념
        • 정보처리기사 필기
        • 정보처리기사 실기 기출
        • 네트워크관리사 2급
        • SQLD
      • 시스템설계
      • Java & Spring
        • TIL
        • 트러블슈팅
        • 고도화
        • 알고리즘
        • 코딩테스트
        • Java
        • Spring
        • Thymeleaf
      • 프로젝트
        • coin-trading
        • 트러블슈팅
      • Docker
      • 웹
      • git & github
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    java two-pointer
    java 메서드
    java 에라토스테네스의 체
    Java 생성자
    Java this
    데이터 타입
    자료구조
    개발로드맵
    java 유클리드 호제법
    java arrays.copyofrnage()
    데이터 크기
    java
    java 멤버
    java기초
    java 제어자
    java 세수의합
    프로그래머스 java 기초트레이닝
    java super
    프로그래머스 java 기초 트레이닝
    java enhance switch
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.1
DJ.Kang
[백준][Gold IV] Java - 1043번 : 거짓말
상단으로

티스토리툴바