[99클럽 코테 스터디 16일차 TIL] 그래프

📖 오늘의 학습 키워드
그래프

오늘의 회고

문제

[방의 개수]
https://school.programmers.co.kr/learn/courses/30/lessons/49190

나의 해결

import java.util.*;
public class Solution {
    public int[][] directions = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

    public int solution(int[] arrows) {
        int answer = 0;
        
        Map<String, Vertex> vertices = new HashMap<>();
        Vertex now = new Vertex(0, 0);
        vertices.put(now.id, now);
        
        for (int idx : arrows) {
            for (int i = 0; i < 2; i++) {
                int x = now.x + directions[idx][1];
                int y = now.y + directions[idx][0];
                String id = Vertex.id(x, y);

                if (!vertices.containsKey(id)) {
                    vertices.put(id, new Vertex(x, y));
                } else if (!now.connectedvertices.contains(id)) {
                    answer++;
                }

                Vertex next = vertices.get(id);
                now.connectedvertices.add(next.id);
                next.connectedvertices.add(now.id);
                now = vertices.get(id);
            }
        }
        
        return answer;
    }
    
    public static class Vertex {
        public int x;
        public int y;
        public String id;
        public Set<String> connectedvertices;

        public Vertex(int x, int y) {
            this.x = x;
            this.y = y;
            this.id = id(x, y);
            this.connectedvertices = new HashSet<>();
        }

        public static String id(int x, int y) {
            return String.format("(%d, %d)", x, y);
        }
    }
}

1. 이차원 배열 directions에 아래 그림 속 숫자 순서로 이동 방향을 저장한다.

2. Vertex 클래스는 방문한 정점의 정보를 담는다.

   • x, y 좌표
   • 해당 정점의 x, y 좌표를 (x, y)형태로 표현한 문자열 id
   • 해당 정점과 연결된 정점들의 좌표(id)를 저장하는 Set

3. 방문한 정점과 그 정점의 정보를 관리하는 Map vertices를 생성한다.

   • key는 해당 정점의 x, y 좌표를 (x, y)형태로 표현한 문자열 id
   • value는 해당 정점의 정보를 담은 Vertex 클래스

4. now는 현재 정점

   • 원점(0,0)에서 출발하므로 이 값으로 초기화하고 vertices에도 추가한다.

5. arrows 배열을 순회하며 정점의 이동을 표현한다.
   1) 이동에 따라 x, y 값을 갱신하고 그 값을 id에 저장한다.
   2) vertices에 id 값이 없으면 처음 방문한 값이므로 새로운 Vertex를 생성하고 이 값을 vertices에 추가한다.
   3) 해당 정점을 재방문했으나 직전 정점과의 간선이 처음 만들어졌다면 방이 새로 만들어진 것이므로 answer에 값을 하나 늘린다.
   4) 현재 정점과 다음 정점을 연결한 간선 정보를 저장한다.

   • 각 정점의 connectedvertices에 다른 정점의 id 값을 추가한다.

   5) 현재 정점 now를 다음 정점 next로 갱신한다.
   6) for (int i = 0; i < 2; i++)가 필요한 이유
   

   • 다음과 같이 교차점이 발생하는 경우 실제 방은 2개 생기지만, 위의 로직대로 라면 1개만 생기게 된다.
   • 그래서 한 번의 이동에 대해 2번씩 실행해 두 칸을 움직이게 한다. 모든 움직임에 대해 두 번 실행했기 때문에 방의 개수를 구하는 결과 값에는 영향을 주지 않는다.

새로 학습한 내용

이번 문제는 혼자 힘으로 풀지 못하고 풀이를 찾아보고 겨우 풀었던 것 같다. 아직은 그래프를 표현하는 부분이 익숙하지 않은 것 같다. 그리고 교차점이 발생해 생기는 예외 케이스를 직접 찾아내는 것 또한 쉽지 않은 것 같다. 앞으로 그래프 문제들을 더 많이 풀어보아야겠다.