[SWEA] 1979. 어디에 단어가 들어갈 수 있을까 (Python/D2)

SW Expert Academy

---

설명

NxN 크기의 단어 퍼즐에서 특정 길이 K를 갖는 단어가 들어갈 수 있는 자리의 수를 출력한다.
검은색으로 칠해진 곳은 단어가 들어갈 수 없다. 흰색으로 칠해진 곳에만 넣을 수 있다. 검은색 = 0, 흰색 = 1
가로 혹은 세로로 단어를 놓을 수 있다. 단어의 길이와 픽셀수는 같아야 한다.

 

풀이

가로와 세로를 나눠서 풀이

1. NxN 퍼즐을 이중 리스트로 입력받는다.

2. 먼저 가로를 한 줄 씩 탐색한다.

• 탐색 중에 픽셀이 1이면, 카운트 값을 증가시킨다.
• 0을 만나면, 카운트 값과 단어 자릿수랑 맞는지 확인한다. 
• 자릿수와 맞으면 결과값 증가 후 카운트값 초기화, 맞지 않으면 카운트값만 초기화한다. 단어 자릿수에 맞게 이어져야 하기 때문에 초기화가 필요하다. 
• 가로 한 줄을 탐색한 후에, 카운트값과 단어 자릿수랑 맞는지 확인한다. 5x5 퍼즐과 단어 길이가 3이라고 할 때, 첫째 줄이 0 0 1 1 1이라고 해보자. 위 과정을 거치면, 0을 만났을 때 자릿수랑 맞지 않으므로 카운트 값은 계속 0이었다가, 1을 만났을 때 카운트 값이 증가한다. 한 줄이 다 끝났을 시점까지도 카운트 값은 증가한다. 한 줄이 다 끝나고 다음 줄 탐색하기 전에, 이 한 줄을 판단하기 위해 필요한 코드이다. 

3. 세로를 한 줄 씩 탐색한다.

• 위의 가로를 탐색할 때와 똑같은데 한 가지 다른 점은, 인덱스의 순서이다. i와 j 위치를 바꿔준다.

4. 탐색이 모두 끝났으면 결과값을 출력한다.

 

Solution

t = int(input())

for tc in range(1, t+1):
    n, k = map(int, input().split())
    puzzle = [list(map(int, input().split())) for _ in range(n)]
    ans = 0 #결과값
    for i in range(n): #가로 확인
        cnt = 0
        for j in range(n):
            if puzzle[i][j] == 1: 
                cnt += 1
            else: #0일 때, 만약 7x7 퍼즐에서 단어가 3자리일 때 가로에서 2가지가 나올 수 있기 때문
                if cnt == k: #카운트값과 단어 자릿수랑 맞으면
                    ans += 1 #결과값에 1을 더하고
                    cnt = 0 #카운트값 초기화
                else: #카운트값과 단어 자릿수랑 맞지 않으면
                    cnt = 0 #결과값은 무시하고, 카운트값 초기화
        if cnt == k: 
            ans += 1
            
    for i in range(n): #세로 확인
        cnt = 0
        for j in range(n):
            if puzzle[j][i] == 1: #인덱스 i, j 주의
                cnt += 1
            else: 
                if cnt == k:
                    ans += 1
                    cnt = 0
                else:
                    cnt = 0
        if cnt == k:
            ans += 1
    print('#'+str(tc), ans)

 

TIL

✔ list(zip(*a)) : 전치행렬을 생성한다.

# 전치행렬 생성
a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
b = list(zip(*a))
b
>>> [(1, 4, 7), (2, 5, 8), (3, 6, 9)]

 

전치행렬 사용

t = int(input())
def calc(puzzle):
    ans = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if puzzle[i][j] == 1:
                cnt += 1
            else:  
                if cnt == k:
                    ans += 1 
                    cnt = 0  
                else: 
                    cnt = 0
        if cnt == k:
            ans += 1
    return ans

for tc in range(1, t+1):
    n, k = map(int, input().split())
    puzzle = [list(map(int, input().split())) for _ in range(n)]
    ans = 0
    ans += calc(puzzle) #가로
    ans += calc(list(zip(*puzzle))) #세로
    print('#'+str(tc), ans)

 

전치행렬을 사용했을 때, 더 간단하게 풀 수 있다.

---

👩‍💻 회고

그래프 탐색 알고리즘을 써야 하나 했지만 굳이 그럴 필요는 없는 문제였다. 현재 위치에서 주변을 탐색할 필요가 없기 때문이다. 카운트를 해주는 것이 핵심이라고 생각한다. 조건을 생각하느라고 시간을 오래 썼다. 

1차 제출에 실패했는데 input 파일 중 6개만 맞았다고 한다. 처음엔 가로 탐색의 else 부분을 이렇게 작성했는데 자세히 보니 j와 i를 반대로 적어서 틀렸던 것이다.. 너무 아쉽다. 그래도 틀린 풀이는 아니라는 생각에 안심이 됐다. 심지어 위의 두 가지 풀이보다 이 코드로 했을 때가 속도와 메모리 상에서 조금 더 효율적이다.

elif puzzle[i][j] == 0 and cnt == k: #0을 만났는데 카운트값과 단어 자릿수랑 같다면
    ans += 1 #결과값 증가
    cnt = 0 #카운트값 초기화
elif puzzle[j][i] == 0: #0을 만나고, 카운트값과 단어 자릿수랑 맞지 않으면
	cnt = 0 #그냥 카운트값만 초기화

 

그래도 더 다양한 방법도 생각할 수 있는 기회가 있었다! 다른 풀이를 보니 대충 다 비슷하게 푼 것 같아서 다행이다. 그리고 전치행렬을 사용해서 반복적인 코드를 만들지 않아도 된다는 것도 알게 됐다.