[프로그래머스] 그래프_방의 개수_Java

💡 코드 작성시 목표는 다음과 같습니다.

1. 시간복잡도를 고려한 효율적인 알고리즘
2. 공간복잡도를 고려한 효율적인 메모리 관리
3. 운영을 위한 단순하고 가독성 높은 코드 작성
4. 다른 개발자에게 안내하기 위한 충분한 주석
5. 해당 문제 외에도 적용할 수 있는 범용성 있는 논리
6. 코딩테스트에서도 활용할 수 있을 만큼 간결한 코드

문제

방의 개수

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.

ex) 1일때는 오른쪽 위로 이동

그림을 그릴 때, 사방이 막히면 방하나로 샙니다.
이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.

입출력 예

arrows	return
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]	3

입출력 예 설명

• (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 arrows 를 따라 그립니다.
• 삼각형 (1), 큰 사각형(1), 평행사변형(1) = 3

제한사항

• 배열 arrows의 크기는 1 이상 100,000 이하 입니다.
• arrows의 원소는 0 이상 7 이하 입니다.
• 방은 다른 방으로 둘러 싸여질 수 있습니다.

해결방안

다음과 같은 조건들을 고려해야 한다.

1. 방문했던 정점(node)을 재방문하는 경우, 방이 생성된다.
2. 기존에 통과한 간선(edge)을 재통과하는 경우에는 정점을 재방문해도 방이 생성되지 않는다.
3. 각 정점(node)의 단위가 작아 간선(edge)끼리의 교차가 발생할 수 있다. 이를 위해 단위를 스케일업 해준다.

기본적인 조건은 위와 같은데, 실제로 문제를 풀었을 때는 아래와 같이 생각할 부분이 많았다.

1. Java의 경우, 좌표에 대한 객체를 만들어야 좌표간 비교가 가능해진다.
   1. hashCode 함수와 equals 함수를 통해 값 비교
   2. 만약 위 두 함수가 없으면 주소값 비교
2. 방문했던 점은 해쉬맵의 키값에 넣고, 그 점과 연결되었던 점들은 리스트화해서 추가한다.
3. 방문할 점의 경우 기존의 점과 연결되어 있는지를 리스트 내에서 확인한 후 카운트를 올려야 한다.

코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Objects;

class Solution {
    static class Pair {
        public int x;
        public int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int hashCode() {
            return Objects.hash(x,y);
        }

        public boolean equals(Object o) {
            return this.x == ((Pair) o).x && this.y == ((Pair) o).y;
        }
    }

    public static int solution(int[] arrows) {

        // 변수 선언
        int cnt = 0;

        // 방향 관련 배열 선언
        Pair pointHC = new Pair(0, 0);
        int[] dx = { 0, 1, 1, 1, 0, -1, -1, -1 };
        int[] dy = { 1, 1, 0, -1, -1, -1, 0, 1 };

        // 방문 여부 관련 선언
        // key = 시작 node의 hashcode, value = 연결된 node들의 hashcode
        HashMap<Pair, ArrayList<Pair>> visitied = new HashMap<>();

        // 로직 처리
        for (int arrow : arrows) {
            for (int i = 0; i <= 1; i++) { // 교차점 처리를 위한 스케일업(반복 2번)

                // 이동 진행
                Pair newPointHC = new Pair(pointHC.x + dx[arrow], pointHC.y + dy[arrow]);

                // 처음 방문하는 경우 = map에 키값이 없는 경우
                if (!visitied.containsKey(newPointHC)) {
                    // 리스트에 연결점 추가
                    visitied.put(newPointHC, makeEdgeList(pointHC));

                    if(visitied.get(pointHC) == null) { // 기존점도 없다면 업데이트
                        visitied.put(pointHC, makeEdgeList(newPointHC));
                    } else { // 기존점이 있다면 추가하기
                        visitied.get(pointHC).add(newPointHC);
                    }   

                // 재방문했고 간선을 처음 통과하는 경우
                } else if (visitied.containsKey(newPointHC) && !(visitied.get(newPointHC).contains(pointHC))) {
                    visitied.get(newPointHC).add(pointHC);
                    visitied.get(pointHC).add(newPointHC);
                    cnt++;
                }

                // 이동 완료
                pointHC = newPointHC;
            }
        }

        return cnt;
    }

    // 밸류값에 넣기 위한 리스트 만들기
    public static ArrayList<Pair> makeEdgeList(Pair pointHC) {
        ArrayList<Pair> edge = new ArrayList<>();
        edge.add(pointHC);
        return edge;
    }

}