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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/49190

코딩테스트 연습 - 방의 개수

 

※주의: 제 코드는 문제를 풀기는 했지만 굉장히 깔끔하지 못한 코드입니다. 더 좋은 풀이가 많으니 다른 풀이도 참고해 보세요!

 

좌표평면에서 시작점을 (0, 0)으로 하고, 0~7에 지정된 이동 방향을 따라 선을 쭉 그린 후, 완성된 방의 개수를 세는 문제입니다.

여기서 방이란, 사방이 선으로 막혀 있는 상태를 방 하나로 센다고 합니다.

 

맨 처음 제가 생각해낸 아이디어는 다음과 같습니다.

"이미 방문했던 좌표에 다시 방문하는 순간 방이 하나 추가된다."

한 번 방문했던 좌표에 다시 도착하는 순간, 사방이 선으로 막혀 있는 상태가 하나 완성된다고 본 것입니다.

[1, 2, 5, 6]을 하면 1개의 방이 완성이 되겠지요.

 

이 아이디어는 몇 가지 문제점이 있습니다.

 

1. [2, 6, 2] 와 같은 움직임이 있다면, 위 아이디어 대로라면 방이 하나 완성되지만, 실제로는 사방이 막혀있는 공간이 생성되지 않으므로 새로운 방이 생성되지 않는다.
   1. [2, 1, 2, 5, 6, 6] 과 같은 움직임을 생각해 보면, 직전에 왔던 길을 되돌아가는 것이 아님에도 불구하고, 왔던 길을 돌아가는 경우에는 방이 생성되지 않는다.
2. [1, 6, 3, 6] 은 위 아이디어에 따르면 방이 하나 완성되어야 하지만, 실제로는 두 개의 방이 완성된다.

 

구체적으로 생각해 봅시다.

1번의 경우, 기존의 아이디어에 더해서, "이미 지나간 경로를 또 지나가는 경우에는 방이 생성되었다고 판단하지 않는다"는 조건을 추가하면 됩니다.

이를 어떻게 구현할 수 있을까요?

"중복을 허용하지 않는 자료구조"를 활용하면 됩니다. 저는 set 자료구조를 활용했어요.

가장 중요한 것은 좌표 a->b와 b->a 경로가 같은 경로로 취급되어야 한다는 점, 즉 지나간 경로에는 방향성이 없다는 점입니다.

이를 위해서 저는 두 좌표를 받은 후, x좌표가 더 작은 쪽, x좌표가 같다면 y좌표가 더 작은 쪽이 앞으로 오도록 하였습니다.

이렇게 두 좌표를 묶은 후 set을 통해 확인을 합니다.

이미 존재하는 경우에는 방으로 간주하지 않고, 존재하지 않는 경우 방을 하나 추가한 후, 해당 경로를 insert 합니다.

 

2번의 경우, 각 좌표 간 거리가 1로 고정이 되어서 생기는 문제라고 할 수 있습니다.

[1, 6, 3, 6]과 같은 경우, 교차점이 (소수점이 아닌 정수로만 나타내야 하므로) 좌표로 표현될 수 없는 곳에 존재한다는 문제점이 원인인 것입니다.

또한, 교차점은 무조건 두 연속된 좌표의 중간점에만 생깁니다. 즉 x좌표 1과 2가 있다면, 이 사이에서 교차하는 좌표는 무조건 1.5가 됩니다.

따라서 저는 이동을 두 배로 늘렸습니다. 한 번 이동할 때마다 두 개의 노드를 지나가는 것으로 간주하고, 각 노드를 지나며 이미 방문한 노드를 지나는 경우를 각각 고려하였습니다.

 

 

지금 보니 main 내의 path_visited는 엄밀히 말하면 경로가 아니라 노드를 기준으로 하는 거니까 node_visited라고 이름짓는 게 더 가독성이 좋아 보이네요.

 

채점 결과

 

잘 풀긴 했지만 제가 별로 안 좋아하는 pair 내에 pair 두 개를 넣는 방법을 썼습니다. 코드 가독성이 지저분해져서...

처음에는 struct를 통해 출발노드와 도착노드 각각의 x, y좌표를 담는 구조체를 만들었는데, 이를 이용한 set 중복 검사가 생각만큼 잘 안 되서 그냥 pair를 사용했습니다.

근데 다른 분들도 그렇게 하신 분들이 많긴 하네요 ㅎㅎ;

 

혹시나 본인이 작성하신 코드가 채점에서 통과가 안 되서 반례가 필요하시다면 더보기를 참고해 주세요.

[6, 5, 2, 7, 1, 4, 2, 4, 6] (정답: 3)
[5, 2, 7, 1, 6, 3] (정답: 2)
[6, 2, 4, 0, 5, 0, 6, 4, 2, 4, 2, 0] (정답: 3)
[7, 2, 5, 2] (정답: 2)

출처: 프로그래머스 방의 개수 질문하기 게시판 및 본인