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

November 12, 2024

🔐 프로그래머스 - 방의 개수

원점에서 주어진 입력대로 이동했을 때, 만들어지는 방의 개수를 세는 문제이다.

한 점에서 출발했을 때, 방이 만들어지기 위해서는 이미 방문했던 점을 다시 지나야 한다.

또한, 이미 방문했던 점을 다시 방문하더라도 방이 만들어지지 않거나, 방을 중복해서 세는

경우를 막아야 하며, 2차원 배열의 정수 점만을 생각해선 안된다.

위 그림처럼 원점에서 출발하여 순서대로 (1,1) → (0,1) → (1,0)으로 이동한다면, 방이 1개

만들어지지만 2차원 배열에서의 방문했던 점을 지난다는 코드로는 이를 검출해낼 수 없다.

따라서 이동을 두 번 하는 방법을 통해 정수 점이 아닌 곳에서 X자로 교차되는 상황을 해결해주었다.

그리고, 이동 경로를 저장하여 방문했던 점을 재방문하고, 경로가 다른 경우만 방을 세주도록 구현하였다.

if (visited.count({nx, ny}) && !path.count({x, y, nx, ny})) {
                answer++;
}