[코드트리 챌린지] 4주차 - 그래프 탐색(BFS)

★ 핵심 : BFS(너비우선탐색)

1. collections의 deque() 활용하기

2. is_vaild() 함수 활용하기

→ r, c 좌표 인덱스가 적절한지 판단

→ board에 이동가능한 곳인지 판단

→ in_queue[r][c]로 방문한 곳인지 판단

---

· 문제링크

https://www.codetree.ai/cote/13/problems/places-can-go?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

· 핵심

1. 출발점이 한 곳이 아니라 동시에 많은 경우

→ 출발점 후보들은 q에 모두 넣고 bfs 한다

for start in stars:
    r, c = start[0] - 1, start[1] - 1
    q.append((r, c))
    in_queue[r][c] = True

2. is_vaild()에서 판단할 것들 

→ 0 <= r < n & 0 <= c < n, r과 c 가 적절한 좌표값인지 

→  in_queue[r][c] 가 False, 즉 방문 하지 않은 곳인지

→  board[r][c] == 0, 이동 가능한 곳인지

---

· 코드(Python)

from collections import deque

def bfs(board, stars):
    n = len(board)
    in_queue = [[False for _ in range(n)] for _ in range(n)]
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]

    def is_valid(r, c):
        return 0 <= r < n and 0 <= c < n and not in_queue[r][c] and board[r][c] == 0

    cnt = 0
    q = deque([])

    for start in stars:
        r, c = start[0] - 1, start[1] - 1
        q.append((r, c))
        in_queue[r][c] = True
        cnt += 1

    while q:
        cr, cc = q.popleft()
        for k in range(4):
            nr = cr + dr[k]
            nc = cc + dc[k]
            if is_valid(nr, nc):
                q.append((nr, nc))
                in_queue[nr][nc] = True
                cnt += 1

    return cnt

n, k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
stars = [tuple(map(int, input().split())) for _ in range(k)]

result = bfs(board, stars)
print(result)

---

※ 실력진단

PS. 학교 과제도 하고 정보처리기사 준비하고 일이 겹치다보니 알고리즘 풀이에 조금 소홀해진 점이 있다. DP 어려운 유형은 아닌데 20분 안에 풀려니까 계속 틀려서 3주 동안 점수가 제자리이다. 다음 주는 분발해야겠다.