백준 20125 쿠키의 신체 측정 Python

🐸 문제 정보

20125번: 쿠키의 신체 측정

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

23.00m

 

📝 풀이

처음에 BFS인가 싶었지만, 사실 동서남북 방향으로 이동하는 경우가 없기 때문에 단순한(?) 구현임을 깨달았다.

처음에 머리 위치와 심장 위치를 알게 된다면, 이후 신체 부위의 길이를 측정하는 것은 어렵지 않았다.

각 방향으로 쭉 이동하면서 거리를 재면 되는데, 여기서 단순한 for문을 사용해도 되지만 나는 처음에 BFS인줄 알고 풀던게 있기 때문에 그냥 deque를 사용해서 풀었다.

 

구현이라 코드 자체는 조금 길지만 어렵지 않은 문제였다.

 

🧑‍💻 나의 답

# pypy3

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().rstrip())
cookie = [list(input().rstrip()) for _ in range(n)]

head = (0, 0)
heart = (0, 0)
groin = (0, 0)
res = []

for i in range(n):
    flag = False
    for j in range(n):
        if cookie[i][j] == '*':
            head = (i, j)
            heart = (i + 1, j)
            flag = True
            break
    if flag: break
def l_a(): #왼팔
    q = deque([heart])
    length = 0
    while q:
        x, py = q.popleft()
        ny = py - 1
        if (0 <= ny) and (cookie[x][ny] == '*'):
            q.append((x, ny))
            length += 1
    res.append(length)

def r_a(): #오른팔
    q = deque([heart])
    length = 0
    while q:
        x, py = q.popleft()
        ny = py + 1
        if (ny < n) and (cookie[x][ny] == '*'):
            q.append((x, ny))
            length += 1
    res.append(length)

def w(): #허리
    global groin
    q = deque([heart])
    length = 0
    while q:
        px, y = q.popleft()
        nx = px + 1
        if (nx < n) and (cookie[nx][y] == '*'):
            q.append((nx, y))
            length += 1
        else:
            groin = (px, y)
    res.append(length)

def l_l(): #왼다리
    q = deque([(groin[0], groin[1] - 1)])
    length = 0
    while q:
        px, y = q.popleft()
        nx = px + 1
        if (nx < n) and (cookie[nx][y] == '*'):
            q.append((nx, y))
            length += 1
    res.append(length)

def r_l(): #오른다리
    q = deque([(groin[0], groin[1] + 1)])
    length = 0
    while q:
        px, y = q.popleft()
        nx = px + 1
        if (nx < n) and (cookie[nx][y] == '*'):
            q.append((nx, y))
            length += 1
    res.append(length)

l_a()
r_a()
w()
l_l()
r_l()

print(heart[0] + 1, heart[1] + 1)
print(*res, sep=' ')