프로그래머스 - 평행 - 완전탐색(조합) - Java

1. 문제

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

핵심 ✨Point

기울기 계산 시 (double)로 반드시 형 변환을 해줘야한다.

2. 구현 풀이

참고 풀이

깊게 생각할 필요가 없었기도 했다. 점은 4개이니까 4 점의 기울기를 구현하면 되는 소스이다.

class Solution {
    public int solution(int[][] dots) {
        int x1 = dots[0][0];
        int y1 = dots[0][1];
        int x2 = dots[1][0];
        int y2 = dots[1][1];
        int x3 = dots[2][0];
        int y3 = dots[2][1];
        int x4 = dots[3][0];
        int y4 = dots[3][1];
        int answer = 0;
        
        double slope1 = (double) (y2 - y1) / (x2 - x1);
        double slope2 = (double) (y4 - y3) / (x4 - x3);
        if (slope1 == slope2) answer = 1;
        
        slope1 = (double) (y3 - y1) / (x3 - x1);
        slope2 = (double) (y2 - y4) / (x2 - x4);
        if (slope1 == slope2) answer = 1;
        
        slope1 = (double) (y4 - y1) / (x4 - x1);
        slope2 = (double) (y2 - y3) / (x2 - x3);
        if (slope1 == slope2) answer = 1;
        
        return answer;
    }
}

2. 완전탐색 풀이

점이 4개 주어지고 서로 평행한 선분이 있는지 확인하는 것.
1, 2, 3, 4번의 점이 있다고 치면 1, 2 / 1, 3 / 1, 4 / 2, 3 / 2, 4 / 3, 4 이렇게 경우의 수를 나눠서 같은 기울기가 있는지 확인하였다.

1. dfs로 경우의 수 구하기.
2. 선택된 두 점과 선택되지 않은 두 점 기울기 파악하기.

import java.util.*;

class Solution {
    boolean[] visit = new boolean[4];
    List<int[]> listComb = new ArrayList<>();
    
    public int solution(int[][] dots) {
        dfs(0, 0, new int[2], dots);
        
        for(int[] A : listComb){
            int[] B = new int[2];
            boolean[] check = new boolean[4];
            
            for(int choice : A){
                check[choice] = true;
            }
            
            int index = 0;
            for(int i = 0; i < 4; i++){
                if(!check[i]){
                    B[index] = i;
                    index++;
                }   
            }
            
            double slope1 = getSlope(dots[A[0]][0], dots[A[0]][1], dots[A[1]][0], dots[A[1]][1]);
			double slope2 = getSlope(dots[B[0]][0], dots[B[0]][1], dots[B[1]][0], dots[B[1]][1]);
            
            if(slope1 == slope2){
                return 1;
            }
        }
        return 0;
    }
    
    public double getSlope(int x1, int y1, int x2, int y2){
        return (double) (y2 - y1) / (x2 - x1);
    }
    
    public void dfs(int depth, int start, int[] arr, int[][] dots){
        if(depth == 2){
            listComb.add(arr.clone());
            return;
        }
        
        for(int i = 0; i < dots.length; i++){
            if(!visit[i]){
                visit[i] = true;
                arr[depth] = i;
                dfs(depth+1, i+1, arr, dots);
                //visit[i] = false;
            }
        }
    }
}