[피드백] BFS문제 정리하기

오늘 알고리즘을 풀며 헷갈렸던 부분, 해결 방법

0. bfs를 해줄때 할 수 있는 장치들

ㅡ 주변의 값을 1씩 증가시켜가며 탐색한다. (모두 탐색하는데 얼마나 걸리는지)

ㅡ 주변의 값을 방문 체크하고 일괄적으로 값을 변경한다.

ㅡ 주변의 값을 체크하면서 count 수를 늘려간다. (탐색하면서 몇개를 만났는지)

 

1. 2차원 배열과 그래프를 접목 시킬때,

list = [[1,2,3,4] , [5,6,7,8] , [9,9,9,9]]

(예)x,y = 1,2 인 부분의 값은

list[y][x] = list[2][1] = 9

 

(예)x,y = 0,1 인 부분의 값은

list[y][x] = list[1][0] = 5

 

2. 2차원 배열(m행 n열) 선언하기

#x,y

#5 7

m,n=map(int,sys.stdin.readline().split())

graph=[[0]*(n) for i in range(m)]

 

3. 뭔가 보인다 보여.. BFS 문제들의 해결 공통점

def bfs(x,y):
	#큐에 넣는다
    q=deque()
    q.append((x,y))
    
    #방문처리 한다
    graph[y][x]=1
    
    #갯수세는 조건이 있다면 변수 선언
    count=1
    
    #큐가 빈상태가 될때 까지 실행
    while q:
    	#가장 앞쪽에 있는것부터 실행
        x,y=q.popleft()
        #주변 탐색을 위한 세팅
        dx=[0,0,-1,1]    
        dy=[-1,1,0,0]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            #경계값 설정
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            #아직 방문하지 않는 노드인지 확인
            if graph[ny][nx] == 0:
                count+=1
                #방문체크
                graph[ny][nx]=1
                #큐에 넣고 그 주변 탐색
                q.append((nx,ny))
    #리턴받은 값 활용하기
    return count

for i in range(n):
    for j in range(m):
    	#원하는 지점부터 탐색을 시작한다
        if graph[j][i]==0:
            answer.append(bfs(i,j))

자주 물어봐야겠다ㅎㅎ