[프로그래머스 : 레벨 5] 방의개수 : HashSet(Java)

이번문제는 방을 찾는거라서 BFS 알고리즘 생각했는데 어떻게 사각형을 표현할지 감이 잡히지 않았다.

(그리고 레벨 5인걸에 쫄기도 했다)

그래서 답을 보게 되었다. 근데 답을 보니 생각보다 이해가 쉬웠다.

답에서는 이번 문제를 수학적인 그래프로 사용을 했다.

 

문제부터 살펴보자.

 

문제 설명

 

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

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

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

 

제한사항

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

 

입출력 예

 

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

 

문제 풀이

 

이번 문제는 x,y 좌표를 이용해서 풀어야 한다.

그리고 해당 좌표를 통해서 생기는 변? 간선?을 Set에 담는다.

따라서 해당 간선이 이미 존재한다면 이미 사각형이 닫힌것이므로 answer++ 시켜주는것이다.

 

x, y 좌표를 결정 짓는 부분은 아래와 같다.

                 if(vect<=1 || vect==7) y++; //0과 1 그리고 7은 위로만 향하기 때문에 y좌표를 ++ 해준다
                 if(1<=vect && vect<=3) x++; //1,2,3은 오른쪽으로 향하기 때문에 x좌표를 ++ 해준다.
                 if(3<=vect && vect<=5) y--; //3,4,5는 아래로 향하기 때문에 y좌표를 --해준다.
                 if(5<=vect && vect<=7) x--; //5,6,7 왼쪽으로 이동하기 때문에 x좌표를 -- 해준다.

이렇게 만들고 위에서 만든 x,y 좌표를 가지고 간선을 만든다.

                 String point = "" + x+"|"+y; // x,y좌표를 String으로 만든다.
                 String normalLine = start +"|" + point; //이전지점 | 현재지점
                 String backLine =  point + "|" + start; // 현재지점 | 이전지점

normalLine과 backLine을 따로 만든 이유는 시작점의 위치가 다를수 있기 때문이다

(1,0)이나 (0,1)은 같기 때문이다.

 

그래서 위에서 만든 간선들이 set에 이미 존재한다면 사각형에 닫히는것이니 answer++ 시켜주고 

해당 간선을 set에다가 넣는다.(어처피 set은 중복제거해주기때문에 상관없다.)

 

 

느낀점

1. 문제에 나와 있는 말을 자세히 살펴보자.(위 문제에선 (0,0) 에서 시작한다는걸봤다면 해결할수 있었을듯)

2. 답지를 보는 습관을 줄이자....