[SWEA/D2] 1954 달팽이 숫자 / BFS

문제 바로가기

SW Expert Academy

나의 코드 및 설명

from collections import deque

def bfs(sx,sy):
    queue = deque()
    queue.append((sx,sy))
    visited[sy][sx] = 1
    num = 1
    count = 0
    while queue:
        if num == n*n:
            return
        x,y = queue.popleft()
        nx = x + dx[count%4]
        ny = y + dy[count%4]
        ##if, else 위치 바꾸면 안됨!
        if 0<=nx<n and 0<=ny<n and visited[ny][nx] == 0:
            nx = nx
            ny = ny
        else:
            count += 1
            nx = x + dx[count%4]
            ny = y + dy[count%4]

        visited[ny][nx] = visited[y][x] + 1
        num+=1
        queue.append((nx,ny))

t = int(input())
for test_case in range(1, t+1):
    n = int(input())
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    visited = [[0]*n for _ in range(n)]
    
    bfs(0,0)
    print("#{}".format(test_case))
    for i in visited:
        print(" ".join(map(str, i)))

피드백

bfs 문제를 연습하지 않았다면 풀지 못했을 문제. 그동안 bfs 문제들을 연습한 덕에 풀 수 있었다. 방문처리는 항상 큐에 append할 때 해주어야 하고, if문에 들어가는 조건의 위치를 함부로 바꾸면 안된다는 것을 알 수 있었다.