구름톤 챌린지 Week 2 - Day 7

https://level.goorm.io/exam/195689/구름-찾기-깃발/quiz/1

문제 자체는 쉽다. 8방위를 모두 뒤졌을 때, 구름이 몇 개 있는지 전부 확인한다.

그런 다음 K가 몇 개있는지 출력하는 문제다. 방위 탐색에 대해 구현한 적이 어렵다면 충분히 어려울 수 있다.

 

def is_valid(x, y, length):
    return 0 <= x < length and 0 <= y < length


LENGTH, K = map(int, input().split())
BOOM = [list(map(int, input().split())) for _ in range(LENGTH)]

dxy = [
  (-1, 0), (1, 0), (0, -1), (0, 1),
  (-1, -1), (-1, 1), (1, -1), (1, 1)
]

answer = 0

for x in range(LENGTH):
    for y in range(LENGTH):
        if BOOM[x][y] == 0:
            boom_count = 0

            for dx, dy in dxy:
                nx, ny = x + dx, y + dy

                if boom_count > K:
                    break

                if is_valid(nx, ny, LENGTH) and BOOM[nx][ny]:
                    boom_count += 1

            if boom_count == K:
                answer += 1

print(answer)

전체 정답 코드이다. 간단하게 설명하면 위에서 언급한 것을 그대로 구현했다.

8방위를 돌면서 구름이 몇 개인지 센다. 그리고 K라면 정답을 1 늘려준다.

이때 탐색하려는 칸에 구름이 있는지 없는지, 범위를 벗어나지는 않았는지 확인해야 한다.

알고리즘 분류를 하자면, 브루트 포스와 구현이라고 할 수 있다.

 

# Case 1
dxy = [
  (-1, 0), (1, 0), (0, -1), (0, 1),
  (-1, -1), (-1, 1), (1, -1), (1, 1)
]

# Case 2
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

# Case 3
dxy = [-1, 1, 0, 0]

방위 표현은 위와 같이 하는 것이 일반적이다.

세 가지 방법이 있는데, 본인이 원하는 방식을 선택하면 된다.

첫 번째는 dxy를 순서쌍으로 선언하여 직접 요소로 받는다. 그리고 dx와 dy를 unpacking하여 사용한다.

두 번째는 dx와 dy를 각각 따로 선언하여 index로 받는다. range(8)을 돌면서 x, y 각각에 dx[i], dy[i]를 더해준다.

마지막은 4방위일 때 효과적이다. 8방위는 식이 더 길어진다.

4방위를 기준으로 설명하면, x가 i번째라고 하면 y는 3-i번째 값이다.

x는 0, 1, 2, 3으로 갈 테고, y는 3, 2, 1, 0으로 간다.

그럴 때 순서쌍으로 나타내보면 (-1, 0), (1, 0), (0, 1), (0, -1)로 첫 번째 방법의 축약 형태임을 알 수 있다.

 

for x in range(LENGTH):
    for y in range(LENGTH):
    
        if BOOM[x][y] == 0:
            boom_count = 0

완전 탐색(brute force)이기 때문에 왕도가 없다. 하나하나 검사해야만 한다.

모든 요소를 하나하나 돌면서, 구름이 있는지 없는지부터 검사한다.

구름이 없다면, boom_count를 0으로 초기화하여 계산할 준비를 한다. 

 

여담으로 cloud_count가 아니라 boom_count로 선언한 이유는 특별하게 없다.

너무나 당연하게 지뢰 찾기라는 브루트 포스 문제로 받아들여서, 나도 모르게 boom으로 선언해버렸다.

 

for dx, dy in dxy:
    nx, ny = x + dx, y + dy

    if boom_count > K:
        break

    if is_valid(nx, ny, LENGTH) and BOOM[nx][ny]:
        boom_count += 1

이 코드는 구름이 없는 칸일 때만 실행하는 코드이다.

위에서 언급한 8방위 방법 중 첫 번째 방법을 사용했다.

8방위를 돌면서, 범위 안에 있으면서 구름이 있는지 확인한다.

is_valid는 코드가 길어져서 따로 함수로 빼, 가독성을 높였다.

말그대로 nx와 ny가 0보다 크고 LENGTH보다 작은지 물어보는 범위이다.

그리고 8방위를 돌면서 구름을 세다가, K보다 커진다면 break로 빠져나온다.

 

def is_valid(x, y, length):
    return 0 <= x < length and 0 <= y < length

 

is_valid() 함수이다.

return 부분이 본 코드에 있으면 가독성이 떨어질 수 있어, 함수로 따로 빼줬다.

 

if boom_count == K:
    answer += 1

마지막으로 boom_count가 K와 같다면 정답에 1을 더해준다.

그럼 모든 K 수를 찾을 수 있다.