[코드트리] BFS 알고리즘 약점 극복 학습 후기

 

이전에 코드트리에서 gap check를 했을 때, bactracking과 bfs 부분이 나왔었다.

오늘은 bfs 문제들을 풀어본 경험을 말해보고자 한다. 

 

우선 코드트리에서는 기본적으로 해당 이론에 대한 설명을 먼저 보여준다.

 

이렇게 이론을 한 번 읽고 예제 문제부터 연습 문제, 심화문제까지 난이도별로 문제를 풀어볼 수 있어 좋다. 

오늘 총 4문제를 풀었는데, 그 중 2문제에 대해서만 다루어 보도록 하겠다.

 

K번 최대값으로  이동하기

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
st_r, st_c = map(int, input().split())

# Please write your code here.
from collections import deque

directions = [(-1,0), (1,0) , (0,1), (0,-1)]

def move(r, c):
    st = grid[r][c]
    q = deque() 
    q.append((r,c))

    visited = [[False]* n for _ in range(n)]
    visited[r][c] = True
    best = None

    while q:
        cur_r, cur_c = q.popleft()
        for dr, dc in directions:
            nr, nc = cur_r + dr, cur_c + dc
            if 0 <= nr <n and 0 <= nc < n and grid[nr][nc] < st and not visited[nr][nc]:
                visited[nr][nc] = True
                q.append((nr,nc))
                cand = (-grid[nr][nc], nr, nc)
                if best is None or cand < best:
                    best = cand
    if best is None:
        return None
    else:
        return best[1], best[2]
        
    

nxt_r = st_r-1
nxt_c = st_c-1

for _ in range(k):
    result = move(nxt_r,nxt_c) 
    if result is None:
        break
    nxt_r, nxt_c = result

print(nxt_r+1, nxt_c+1)

이 문제를 풀 때, 처음에는 가능한 값들에 대해 리스트로 받은 후 정렬을 했는데

이후 리팩토링 과정에서 튜플에 대한 비교연산자가 사용 가능함을 인지하고 위와 같이 바꿔주었다. 

또한 더 이상 움직일 수 없는 경우 k번 만큼 반복하지 않도록 하기 위해 return 값을 None으로 설정해 즉시 종료할 수 있도록 하였다.

 

 

돌 잘 치우기

n, k, m = map(int, input().split())

grid = [list(map(int, input().split())) for _ in range(n)]

r = []
c = []
for _ in range(k):
    ri, ci = map(int, input().split())
    r.append(ri - 1)
    c.append(ci - 1)

# Please write your code here.
directions = [(-1,0), (1,0), (0,1), (0,-1)]
from collections import deque
rocks = []

for i in range(n):
    for j in range(n):
        if grid[i][j]:
            rocks.append((i,j))

import itertools

def bfs(board):
    q = deque()
    cnt = 0

    for i in range(k):
        q.append((r[i],c[i]))
        board[r[i]][c[i]] = 1
        cnt += 1

    while q:
        cur_r, cur_c = q.popleft()
        for dr, dc in directions:
            nr , nc = cur_r + dr, cur_c + dc
            if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:
                board[nr][nc] = 1
                q.append((nr,nc))
                cnt += 1
    return cnt

ans = 0
import copy
for case in itertools.combinations(range(len(rocks)), m):
    temp = [row[:] for row in grid]
    for clean in list(case):
        temp[rocks[clean][0]][rocks[clean][1]] = 0
    #print(temp)
    cnt = bfs(temp)
    ans = max(ans, cnt)


print(ans)

여기서 신경쓸만한 부분은 itertools의 combinations를 잘 활용하는 것. 

가끔 바로 len(rocks)와 같이 int를 넣어서 에러가 나는 경우가 있는데 항상 iterable한 값이 첫번째 인자로 들어가야함을 인지하자.

 

그리고 copy의 부분인데,,, 

1차원의 경우는 문제가 없지만 2차원의 경우는 copy()를 통했을때 내부만 만들고 포인터간 연결이 되어버리기에 유념해야 한다. 

그래서 얕은 복사/깊은 복사가 필요한 경우를 잘 구분해 copy라이브러리의 copy()나 deepcopy()를 활용해야 하는데,

deepcopy()는 메모리를 많이 잡아먹기 때문에 주의해서 사용해야 한다.

위에서와 같이 temp = [row[:] for row in grid]와 같이 얕은 복사를 해주는게 가장 간편하고, 또 파이썬 다운 코드라고 생각한다.

 

 

항상 각 문제들을 풀때 다른 방법으로, 최적화를 더 해서 풀어보려고 노력한다.

 

BFS 문제들을 풀어보며 느낀 점은... 

• bfs를 함수로 정의할 것인가. (재사용 하는가)
• deque()에 어떤 값을 넣을 것인가. (r,c, + 특정 값)
• 예외 case / 탈출 case가 어떤 경우인가.
• board/grid를 재사용한다면 변수명에 주의하며, 얕은/깊은 복사 하기.
• visited가 별도로 필요한가? 배열로 할 것인가 set으로 할것인가.
• 범위 체크 잘하기. (격자의 좌표가 1부터 시작하는 case)
• 디버깅시 격자 출력법 : for row in grid: print(row)
• BFS의 O(N·M)에 대해 시간복잡도 미리 계산 필요.

위의 요정도 것들만 고민해서 문제를 푼다면 괜찮지 않을까..? 란 생각이다.

 

사실 단순 BFS는 크게 어렵다고 생각을 안하고, 여러가지 상황을 엮거나 하는 경우 (마치 시뮬레이션)

그런 경우에는 난이도가 좀 올라간다고 생각은 한다. 다음에 좀 더 많은 문제를 풀어보도록 하겠다.

 

다른 사람의 풀이도 볼수 있고, 기존 백준과 달리 해설코드도 별도의 설명과 함께 존재하기 때문에

PS를 연습해야 한다면 코드트리를 활용해보는걸 권장한다.

---

 

K번 최댓값으로 이동하기 설명 | 코드트리

 

돌 잘 치우기 설명 | 코드트리