[코딩테스트] BFS 보다 더 익숙해지기

계속 DFS로 푸는게 익숙해서 BFS가 너무 어렵다..

익숙해지자! 화이팅!

https://www.acmicpc.net/problem/10026

풀이는 아래 분 및 다양한 블로그 포스팅들을 참고
https://www.youtube.com/watch?v=xzOEbKqQQC4&t=314s
https://www.youtube.com/watch?v=-daSs-maaVk

10026번: 적록색약

 

이 문제에서 알아야 하는 아이디어 
[1] 이 유형은 BFS의 기본 유형으로, 여느 유형처럼 노드 별로 방문을 tracking하고 방문한 경우 이를 업데이트해서 재방문하지 않도록 하고, 같은 색은 지속적으로 방문

[2] 그렇게 loop를 돌면서 현재 바라보는 노드에서 쭉 BFS를 수행, 끝나고 나서 그 다음 loop에서 여전히 0인 것이 있으면 그것은 색이 변한 경우이므로 cnt+=1 수 

from collections import deque
N = int(input())
maps = [[x for x in input()] for _ in range(N)]
visited = [[0]*N for _ in range(N)]
move_x = [-1,1,0,0]
move_y = [0,0,1,-1]
cnt = 0

def BFS(maps,queue,flag=False) :
    while queue :
        x, y = queue.popleft()
        current_col = maps[x][y]
        visited[x][y] = 1

        for k in range(4) :
            after_x = x+move_x[k]
            after_y = y+move_y[k]
            if after_x < 0 or after_y < 0 or after_x >= N or after_y >= N :
                continue
      
            if not flag : 
                if visited[after_x][after_y] == 0 and maps[after_x][after_y] == current_col :
                    visited[after_x][after_y] = 1
                    queue.append([after_x,after_y])
            elif flag :
                if visited[after_x][after_y] == 0 :
                    if current_col == 'R' or current_col == 'G' :
                        if maps[after_x][after_y] in ['R','G'] :
                            visited[after_x][after_y] = 1
                            queue.append([after_x,after_y])
                    else :
                        if maps[after_x][after_y] == current_col :
                            visited[after_x][after_y] = 1
                            queue.append([after_x,after_y])

##### 이 문제에서 알아야 하는 아이디어 
#### 이 유형은 BFS의 기본 유형으로, 노드 별로 방문을 tracking하고 방문한 경우 이를 업데이트해서 재방문하지 않도록 하고, 같은 색은 지속적으로 방문
#### 그렇게 loop를 돌면서 현재 바라보는 노드에서 쭉 BFS를 수행, 끝나고 나서 그 다음 loop에서 여전히 0인 것이 있으면 그것은 색이 변한 경우이므로 cnt+=1 수 
for i in range(N) :
    for j in range(N) :
        queue = deque()
        queue.append([i,j])
        if visited[i][j] == 0 :
            BFS(maps,queue)
            cnt+=1

visited = [[0]*N for _ in range(N)]
cnt_blind = 0
for i in range(N) :
    for j in range(N) :
        queue = deque()
        queue.append([i,j])
        if visited[i][j] == 0 :
            BFS(maps,queue,True)
            cnt_blind+=1

print(cnt,end= ' '); print(cnt_blind)

 

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

이 문제에서 알아야 할 아이디어 
[1] 탐색한 노드의 다음 이웃 노드들이 아니라, 먼저 감염이 된 같은 날의 토마토를 기준으로 BFS를 수행해야 함

[2] 따라서 queue에 주변 노드가 아니라, 감염된 노드부터 먼저 봐주어야 하기 때문에 먼저 감염되어 있는 토마토를 queue에 집어넣음

[3] 입력되는 map에 누적되는 값을 통해 일자를 tracking 할 수 있음

 

m, n = [int(x) for x in input().split()]

maps = [[int(x) for x in input().split()] for _ in range(n) ]

from collections import deque

queue = deque()

############### 이 문제에서 알아야 할 아이디어 (1)
########## 탐색한 노드의 다음 이웃 노드들이 아니라, 먼저 감염이 된 같은 날의 토마토를 기준으로 BFS를 수행해야 함
########## 따라서 queue에 주변 노드가 아니라, 감염된 노드부터 먼저 봐주어야 하기 때문에 먼저 감염된 토마토를 아래 for loop를 통해 queue에 집어넣음
for i in range(n) :
    for j in range(m) :
        if maps[i][j] == 1 :
            queue.append([i,j])

move_x = [-1,1,0,0]
move_y = [0,0,1,-1]


### 언제를 하루 기준으로 잡아야할까?
while queue :
    x, y = queue.popleft()

    for k in range(4) :
        after_x = x+move_x[k]
        after_y = y+move_y[k]

        if after_x < 0 or after_y < 0 or after_x >= n or after_y >= m :
            continue

        if maps[after_x][after_y] == 0 :
            queue.append([after_x,after_y])
            #################### 이 문제에서 알아야 할 아이디어 (2)
            ######## 누적되는 값을 통해 일자를 tracking 할 수 있음
            maps[after_x][after_y] = maps[x][y] + 1
            
flag = False
answer = 0

### 여기 마이너하지만 조건 체크 조심하자
for row in maps :
    if 0 in row :
        flag = True
        break
    answer = max(answer,max(row))

if flag :
    print(-1)
else :
    print(answer)