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

🏠 프로그래머스 Level 5 – 방의 개수(Java) 풀이

이번에 풀어본 문제는 프로그래머스에서 난이도가 꽤 높은 편에 속하는 ‘방의 개수’ 문제다.
단순히 격자를 탐색하는 문제가 아니라, 좌표평면을 이동하면서 생기는 “교차”를 통해 방의 개수를 세는 문제라서 구현 난이도가 꽤 있다.

방이 생기는 조건은 의외로 단순하다.

이미 방문한 정점을 다시 방문하는데,
그 정점으로 들어오는 간선(길)이 처음 등장하면 → 새로운 방 생성!

이 규칙 때문에 정점 방문 여부뿐 아니라 간선 방문 여부까지 저장해야 한다.

---

🔎 핵심 아이디어

✔ 방향 이동은 8방향 (0~7)

문제에서 주어진 대로
dx, dy로 8방향 이동을 정의한다.

✔ 보통 이동하면 노드 간 간선은 1개지만, 이 문제는 ‘대각선 교차’ 때문에 2번 이동해야 함

대각선 교차가 생기면 방이 생기는데,
이를 제대로 잡으려면 한 칸을 절반씩 2번 이동시켜서 교차를 처리한다.

그래서 for문에 for(int i=0; i<2; i++) 가 들어간다.

✔ 방문 체크

• visitedE : 방문한 정점(노드)
• visitedV : 방문한 간선(길)
• 간선은 방향성이 있으므로 "x1,y1-x2,y2" 형태로 저장

✔ 방이 생기는 순간

• 다음 노드(e2)가 이미 방문된 정점이면서
• 현재 이동 경로(e1→e2)가 처음 등장한 경우
  → 새로운 방이 생김

---

🧩 코드 (Java)

아래는 내가 작성한 최종 코드다.

 

import java.util.*;

class Solution {
    public int solution(int[] arrows) {
        int answer = 0;
        Set<String> visitedE = new HashSet<>();
        Set<String> visitedV = new HashSet<>();
        
        int[] dx = {1,1,0,-1,-1,-1,0,1};
        int[] dy = {0,1,1,1,0,-1,-1,-1};       
        
        int x = 0, y = 0;
        visitedE.add("0,0");
        
        for(int a : arrows){
            for(int i = 0; i < 2; i++){
                int nx = x + dx[a];
                int ny = y + dy[a];
                
                String e1 = x + "," + y;
                String e2 = nx + "," + ny;
                String v1 = e1 + "-" + e2;  // 방향 있는 간선
                String v2 = e2 + "-" + e1;  // 반대 방향 간선
                
                // 방문한 점이지만 간선은 처음 방문 → 새로운 방
                if(visitedE.contains(e2) && !visitedV.contains(v1)){
                    answer++;
                }
                
                visitedE.add(e2);
                visitedV.add(v1);
                visitedV.add(v2);
                
                x = nx;
                y = ny;
            }
        }
        
        return answer;
    }
}

---

📘 흐름 요약

1. 시작점 (0,0)
2. 8방향 이동 → 대각선 교차 대비해서 2번씩 이동
3. 정점 방문 여부 체크
4. 간선 방문 여부 체크
5. • 정점은 방문된 곳인데
   • 간선은 처음 나왔다면 → 방 +1
6. 최종 answer 반환

---

🎯 정리

이 문제의 핵심은 정점 방문과 간선 방문을 구분해서 관리하는 것
그리고 대각선 교차 방지를 위해 이동을 ‘반칸씩 2번’ 나누어 구현하는 것이다.

처음 보면 복잡해 보이지만 원리는 굉장히 논리적이라,
그래프 문제 좋아하는 사람이라면 꼭 한 번 풀어볼 만한 문제다.