[김태원 알고리즘] 사과나무 (BFS)

사용 언어: Python3

문제

풀이

내 풀이

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

ans = 0
src, dst = N//2, N//2
for i in range(N//2 + 1):
    for j in range(src, dst+1):
        ans += board[i][j]
    src, dst = src-1, dst+1

src, dst = 1, N-2
for i in range(N//2 + 1, N):
    for j in range(src, dst+1):
        ans += board[i][j]
    src, dst = src+1, dst-1

print(ans)

다른 풀이 - BFS 사용

from collections import deque

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

q = deque()
q.append((N//2, N//2))
visited[N//2][N//2] = 1
ans = board[N//2][N//2] # 중앙값 넣어놓기

L = 0 # ✅ Level 0부터 시작
dx, dy = [0,-1,0,1], [1,0,-1,0]
while True:
    if L == N//2: # ✅ break 조건 중요!
        break
    for _ in range(len(q)): # ✅ 큐의 길이만큼 돌기 🌟
        cur = q.popleft() # 하나 꺼내서
        for w in range(4): # 네 방향 탐색
            xx, yy = cur[0]+dx[w], cur[1]+dy[w]
            if xx<0 or xx>=N or yy<0 or yy>=N:
                continue
            if visited[xx][yy] == 1:
                continue
            q.append((xx, yy))
            ans += board[xx][yy]
            visited[xx][yy] = 1
    L += 1 # ✅ Level + 1

print(ans)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기