쿼드압축 후 개수 세기 (c++)

1. 문제

코딩테스트 연습 - 쿼드압축 후 개수 세기 | Programmers School

프로그래머스

2. 풀이

문제에서 2차원 정수 배열을 쿼드 트리와 같은 방식으로 압축하기를 주제로 줬다.

전체가 동일한지 확인하고, 맞으면 압축 아니면 더 작은 부분끼리 확인하고 하는 방식이라서 재귀함수를 사용해야할 것 같다고 생각했다. 조건을 주고 더 이상 비교할 수 없을 때까지 재귀함수를 돌렸는데, 찾아보니까 이렇게 푸는 방법이 바로 'dfs'였다. 그냥 풀었는데 dfs로 풀고있었다.

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog (gmlwjd9405.github.io)

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

1. x, y, size를 주고 arr[x][y]를 기준으로 size만큼 반복문 돌리면서 0과 1 확인

• 처음에는 arr[x][y] == arr[x][y+1]으로 비교했는데, 2차원 배열이라서 가로값이랑만 비교하는게 아니라 세로값이랑도 비교해야해서 계속 오류가 났다.
• 후에 0이랑 1이랑 있는지 없는지 확인하는 int one, zero를 따로 만들어서 (one && two)로 전부 동일한지 확인

2. 전부 동일하면 answer의 맞는 인덱스에 +1 & 쿼드 압축하기

• 최종 압축된 배열에서 압축되지 않은 1과 0은 그냥 따로 셀 예정이어서, 전부 동일하게 되서 압축된 부분은 그냥 버리는 값으로 만들기 위해 다른 값 삽입
• 실행했을 때 보기 편하려고 1이 압축된 곳은 3으로, 0이 압축된 곳은 2로 통일

3. 동일하지 않아 압축이 되지 않은 경우 dfs로 다시 탐색

3. 생각

• dfs에 대한 이론 공부를 해볼 필요가 있다고 느꼈다.

 

shin0112/programmers_cpp: programmers' coding test solutions (github.com)

출처 : 프로그래머스 코딩 테스트 연습 - 쿼드압축 후 개수 세기
https://school.programmers.co.kr/learn/courses/30/lessons/68936#