[PS] BFS 최적화

from collections import deque

dx, dy = [1,-1,0,0], [0,0,1,-1]

def solve():
    m, n, k = list(map(int, input().split()))
    
    def isValid(x, y):
        return 0 <= x < m and 0 <= y < n
        
    Map = [[0 for _ in range(m)] for _ in range(n)]
    visit = [[False for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        x, y = list(map(int, input().split()))
        Map[y][x] = 1

    cnt = 0
    for y in range(n):
        for x in range(m):
            if(Map[y][x] == 0 or visit[y][x] == True):
                continue
            cnt += 1
            Q = deque([(x, y)])
            while(len(Q)):
                cx, cy = Q.popleft()
                visit[cy][cx] = True 
                for i in range(4):
                    nx, ny = cx + dx[i], cy + dy[i]
                    if(isValid(nx, ny) and Map[ny][nx] == 1 and visit[ny][nx] == False):
                        Q.append((nx, ny))
                        
                
    print(cnt)      

그룹의 개수를 세는 문제
이미 시간복잡도는 최적이고 로직은 맞지만, visit처리를 하는 위치에 따라 조금 더 성능이 좋아진다.

from collections import deque

dx, dy = [1,-1,0,0], [0,0,1,-1]

def solve():
    m, n, k = list(map(int, input().split()))
    
    def isValid(x, y):
        return 0 <= x < m and 0 <= y < n
        
    Map = [[0 for _ in range(m)] for _ in range(n)]
    visit = [[False for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        x, y = list(map(int, input().split()))
        Map[y][x] = 1

    cnt = 0
    for y in range(n):
        for x in range(m):
            if(Map[y][x] == 0 or visit[y][x] == True):
                continue
            cnt += 1
            Q = deque([(x, y)])
            visit[y][x] = True
            while(len(Q)):
                cx, cy = Q.popleft()
                for i in range(4):
                    nx, ny = cx + dx[i], cy + dy[i]
                    if(isValid(nx, ny) and Map[ny][nx] == 1 and visit[ny][nx] == False):
                        Q.append((nx, ny))
                        visit[ny][nx] = True
                
    print(cnt)     

달라진 점: visit을 실제 방문했을 때가 아닌 queue에 푸시하는 시점에 하면 중복 삽입을 피할 수 있다.

before:

while(len(Q)):
	cx, cy = Q.popleft()
    visit[cy][cx] = True 
    for i in range(4):
    	nx, ny = cx + dx[i], cy + dy[i]
        if(isValid(nx, ny) and Map[ny][nx] == 1 and visit[ny][nx] == False):
        	Q.append((nx, ny))

after:

while(len(Q)):
	cx, cy = Q.popleft()
    for i in range(4):
    	nx, ny = cx + dx[i], cy + dy[i]
        if(isValid(nx, ny) and Map[ny][nx] == 1 and visit[ny][nx] == False):
        	Q.append((nx, ny))
        	visit[ny][nx] = True

+) x, y for문에 쓴 iteration 변수 그대로 썼다가 틀렸으니 조심
x, y 대신 -> cx, cy