[백준] 1652번 누울 자리를 찾아라 파이썬 해설 (Python)

출처 : https://www.acmicpc.net/problem/1652

1652번: 누울 자리를 찾아라

수학 알고리즘 문제로 분류된 문제이다.

문제를 잘못 이해해서 한 번에 맞추지 못했던 문제여서 억울함이 가득한 문제이다.
해설을 보기 전에 문제를 다시 한번 정독한 뒤 다시 풀어보는 것을 추천한다!

 

풀이

---

문제에 그림이 나오고 입력이 특이하다고 겁먹지 말고 문제를 천천히 읽어보면 그리 어렵지 않은 문제라는 것을 알 수 있다.

문제에서 원하는 출력인 "가로로 누울 수 있는 자리"와 "세로로 누울 수 있는 자리"는 다음과 같이 정리할 수 있다.

1. 가로방향 혹은 세로방향으로 연속해서 2칸 이상의 빈칸이 존재하면 누울 수 있다.
2. 무조건 벽이나 짐에 닿아야 "자리"라고 정의할 수 있다.

2번 경우는 아래 그림을 보면 이해하기 쉽다.

왼쪽의 빨간 사각형 부분이 짐이 있는 위치라고 한다면 짐 양옆으로 두 개의 "누울 수 있는 자리"가 생기고,
오른쪽처럼 장애물이 없는 경우 2번 조건에 의해 한 개의 "누울 수 있는 자리"는가 생긴다.

 

문제 풀이 순서
1. 한 줄씩 배열을 입력받는다.
2. 한 줄씩 입력을 받으면서 입력받은 줄에 대해서 바로 "가로로 누울 수 있는 자리"의 개수를 파악한다.
3. 모든 입력이 끝나면 "세로로 누울 수 있는 자리"의 갯수를 파악한다.
4. 출력

 

- 정답 코드

import sys
input=sys.stdin.readline

def find_row(arr):
    cnt = 0
    row_cnt = 0
    for char in arr:
        if char == '.': cnt += 1
        else:
            if cnt >= 2:
                row_cnt += 1
                cnt = 0
            else: cnt = 0
    if cnt >= 2: return row_cnt + 1
    else: return row_cnt

def find_col(arr):
    col_cnt = 0
    l = len(arr)
    for i in range(l):
        cnt = 0
        for j in range(l):
            if arr[j][i] == '.' : cnt += 1
            else:
                if cnt >= 2:
                    col_cnt += 1
                    cnt = 0
                else: cnt = 0
        if cnt >= 2 : col_cnt += 1
    return col_cnt

if __name__ == "__main__":
    arr = []
    row_cnt, col_cnt = 0, 0
    for i in range(int(input())):
        arr.append([])
        for j in input().rstrip():
            arr[i].append(j)
        row_cnt += find_row(arr[i])

    col_cnt = find_col(arr)
    print(row_cnt, col_cnt)

* 가로방향 탐색과 세로 방향 탐색 각각 사용하는 함수의 형태는 조금 다르지만 알고리즘은 비슷하다.

 

결과 인증

---

문제를 잘못 읽어서 네 번만에 풀 수 있었던 문제이다. 이런 실수는 실전에서 엄청난 시간 낭비를 초래할 수 있으니 나처럼 실수하지 말고 한 번의 시도만에 문제를 푸는 연습을 하길 바란다.