구름톤 챌린지 Week-2 / 7일차 미션

7일차 미션 - 주변 구름 탐색하기

<유형>

행렬이 주어지고 모든 index 에 대해 탐색하는, 전형적인 완전탐색 문제이다.

평소에 코딩테스트에 관심이 많았던 사람이라면 손쉽게 풀었을 거라 생각한다.그렇게 생각하자마자 정답율이 이미 98퍼센트...

핵심 아이디어

사실 그냥 완전 탐색을 하는 문제라 대부분의 사람은 어렵지 않았을 거라 생각하지만, 나는 오랜만에 문제를 푸는 거라 아이디어가 쉽게 떠오르지 않았다ㅠㅠ바보인듯ㅋ

그래서 핵심은

=> 인덱스 체크를 위한 x,y 방향의 배열을 만들어 놓는 것이 다이다.

# 인덱스 체크
# 시계방향체크, y,x 가 움직이는 방향만 맞으면 됨ㅇㅇ
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1 ]

이후는 이중 for 문 안에서 매트릭스의 각 칸마다 주변 8칸을 시계방향으로 돌면서 아래 사항을 체크하면 된다.
1. 구름이 있는지?
2. 매트릭스의 크기를 벗어나는 지?

#...위에 코드는 초기화 및 이중 for 문 시작
				# 구름이면 건너뛰셈
				if m[i][j] == '1':
                    continue
				
                #인덱스 마다 나온 깃발 개수 count
                cnt = 0
                # 시계 방향으로 인덱스 check
                for t in range(8):
                	# 현재 인덱스에 더해서 check 하면 됨
                    ny = i + dy[t]
                    nx = j + dx[t]
                    # 맵을 안 넘치고, 주변에 '1'(구름)이 있다면 cnt 증가
                    if 0 <= ny < N and 0 <= nx < N and m[ny][nx] == '1': 
                        cnt += 1
                
                # 찾는 깃발 개수면 result 에 case 더하기
                if cnt == k:
                    result += 1

for 문이 많아서 불편할 수도 있지만, 논리대로 코드를 쓰면 완전탐색유형의 문제는 모두 저런 식이다.

만약에, 많이 중첩된 for문 안에서 인덱스를 모두 돌면서 cnt 를 증가시키고, 깃발 개수 check하고, result 저장하는게 맘에 안 들면(왠지는 모름ㅋ), cnt 배열을 매트릭스 크기만큼 만들어서 cnt 를 저장하고 나중에 비교하자ㅇㅅㅇ
코드 더 길어져서 불편한 건 비밀임ㅋㅋ

공부 좀 많이 해야겠다. 5초만 고민하고 풀어버리고 싶음