👩‍🎓공부 - 2024.01.16 오늘의 백준 문제풀이

27211번 - 도넛 행성

탐색을 하는데 그래프가 주어지면 제한이 없습니다! 이게 무슨 말이냐면

if nx<0 or ny<0 or nx>=N or ny>=M:
	continue

저희가 보통 BFS나 DFS를 사용하게 되면 이런 씩으로 그래프를 넘어갈 시 continue를 시키지 않습니까?

근데 이 그래프는 위와 같이 도넛모양의 형태여서 넘어가도 그대로 넘어간 만큼 연산처리를 하는 문제입니다. 예를 들어 가로길이가 5고 현재 가로인덱스가 5일때 오른쪽 탐색을 하면 평소대로라면 그래프를 넘어서 list out of index 오류를 방지하기 위해 continue를 넣어줄 텐데 이 문제는 그래프가 도넛 형식이므로 5->1로 넘어가 다시 1번 인덱스를 탐색해야 합니다.

N,M = map(int,input().split())
graph = []
que = deque()
for _ in range(N):
    graph.append(list(map(int,input().split())))
visited = [[0]*M for _ in range(N)]

BFS 탐색을 위한 입력을 받아줍시다. visited로 방문여부 표시도 준비하겠습니다.

cnt = 0
for i in range(N):
    for j in range(M):
        if not visited[i][j]:
            if graph[i][j] == 0:
                bfs(i,j)
                cnt += 1

0은 빈 공간이고 1은 숲이라 탐색하지 못하는 공간이므로 for문을 돌려서 0이 나온다면 그 구간을 탐색해주겠습니다. 탐색이 완료되면 cnt변수를 하나 높여서 나중에 답을 도출할 때 써먹을 수 있도록 하겠습니다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]

deque를 import 해주고 상하좌우 설정을 해줍니다.

def bfs(x,y):
    que.append([x,y])
    visited[x][y] = 1
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

여기까진 평범한 DFS와 동일합니다. 방문여부 표시해주고 4방향 탐색을 돌려주면 됩니다.

            if nx>=N:
                nx = nx%N
            if ny>=M:
                ny = ny%M
            if nx<0:
                nx = N + nx 
            if ny<0:
                ny = M + ny

여기서 이제 x, 즉 세로값이 세로의 길이인 N을 넘어가게 되면 세로값을 N으로 나눈 나머지가 결과적으로 다음 탐색할 인덱스가 됩니다. 가로도 마찬가지입니다.

만약에 x가 0 이하여서 음수가 나오게 생긴 상황이라면 N에 해당 음수를 더한 값이 다음 탐색할 인덱스가 됩니다. 예)N은 5, 현재 인덱스가 0이고 상 탐색하여 nx가 -1이 되었는데 위 연산을 통해 가로 최대 높이인 5-1=4를 탐색할 수 있음

            if not visited[nx][ny]:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = 1
                    que.append([nx,ny])

물론 이 모든 조건은 방문을 하지 않았고 빈 공간(0) 이라는 조건이 수반되어야만 이뤄지는게 가능합니다.

print(cnt)     

출력하면 정상적으로 답을 도출할 수 있습니다.

실수사항

저는 파이썬 언어의 특징상 음수처리는 0인덱스에서 -1빼면 -1인덱스에 접근하여

            if nx<0:
                nx = N + nx 
            if ny<0:
                ny = M + ny

해당 구문은 딱히 필요 없을 줄 알았는데 60퍼쯤 가서 틀렸습니다 가 나왔습니다.
아마 -2가 나온다던지, x와 y값이 둘다 음수가 나온다던지 하면 변수가 있는 것 같습니다.