아찌방 하우스

https://school.programmers.co.kr/learn/courses/30/lessons/43162

풀이 - 나의 생각

방문을 하면서

시작점을 기록합니다.

ex. A에서 시작해서 도착한 곳은 다 A로 저장

그 후에 Set으로 저장된 시작점의 개수를

중복없이 세면

네트워크의 개수가 나옵니다.

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int[] network = new int[n];
        Queue<Integer> q = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(computers[i][j] == 0) continue;
                if(network[j] > 0) continue;
                q.offer(j);  
            }
            
            while(!q.isEmpty()){
                int computer = q.poll();
                network[computer] = i+1;
                
                for(int j = 0; j < n; j++){
                    if(computers[computer][j] == 0) continue;
                    if(network[j] > 0) continue;
                    q.offer(j);
                }
            }
        }
        
        for(int k : network){
            set.add(k);
        }
        return set.size();
    }
}

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

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

코드

BFS 풀이 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class JUN12886 {
    static int sum;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        sum = A + B + C;
        visited = new boolean[sum+1][sum+1];

        if(sum % 3 != 0){
            System.out.println("0");
            return;
        }

        Queue<int[]> q = new ArrayDeque<>();

        q.offer(new int[]{A,B,C});
        visited[A][B] = true;

        boolean flag = false;
        while (!q.isEmpty()){
            int[] now = q.poll();
            int a = now[0];
            int b = now[1];
            int c = now[2];

            if(a == b && b == c) {
                flag = true;
                break;
            }

            for (int i = 0; i < 2; i++) {
                for (int j = i+1; j < 3; j++) {
                    if(now[i] == now[j]) continue;
                    int t1 = now[i] > now[j]? now[i] - now[j] : now[i] + now[i];
                    int t2 = now[i] > now[j]? now[j] + now[j] : now[j] - now[i];
                    if(!visited[t1][t2]){
                        visited[t1][t2] = true;
                        q.offer(new int[]{t1, t2 ,sum - (t1 + t2)});
                    }
                }
            }
        }

        System.out.println(flag?"1":"0");
    }
}

DFS 풀이 방식

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

public class Main {
    static int sum;
    static int[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        sum = A + B + C;
        visited = new int[sum+1][sum+1];

        if(sum % 3 != 0){
            System.out.println("0");
        }else {
            dfs(A,B);
            System.out.println(visited[sum/3][sum/3]);
        }
    }

    public static void dfs(int a, int b){
        if(visited[a][b] == 1) return;

        visited[a][b] = 1;

        int[] now = {a, b, sum - (a+b)};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(now[i] < now[j]) {
                    int[] temp = {a, b, sum - (a + b)};
                    temp[i] += now[i];
                    temp[j] -= now[i];
                    dfs(temp[0], temp[1]);
                }
            }
        }
    }
}

풀이

 A + B + C = sum 

이 세가지 돌 그룹의 합은

돌을 이동 시켜도 변하지 않는다.

또한

C = sum - ( A + B)

와 같이 

한 돌 그룹의 값은

sum 값에서 나머지 두 그룹의 합을 뺀 값과 같다

 두 그룹을 비교하다 보면

결국 반복된다.

-> 중복 처리 필요