[코드트리] BFS/DFS - 돌 잘 치우기

김멉덥·2024년 4월 29일
0

알고리즘 공부

목록 보기
143/171
post-thumbnail
post-custom-banner

코드트리 학습하기 - 알고리즘 입문 : BFS/DFS

Code

from collections import deque
from itertools import combinations

n, k, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
start_point = [list(map(int, input().split())) for _ in range(k)]

rock_list = []

ans = []

# 돌이 있는 위치의 [x, y] 를 rock_list에 모두 담아주기
for i in range(n):
    for j in range(n):
        if(matrix[i][j] == 1):
            rock_list.append([i, j])

pick_rock = list(combinations(rock_list, m))        # 돌이 있는 위치에서 제거할 m개의 돌을 뽑는 모든 조합 구해서 pick_rock 리스트에 담기
# print(pick_rock)

# 기존 matrix에 저장된 값을 복사해서 반환해주는 함수 (원본 matrix 배열을 변형시키지 않기 위함)
def copy_matrix(matrix):
    cp = []
    for i in range(len(matrix)):
        sub = []
        for j in range(len(matrix[i])):
            sub.append(matrix[i][j])
        cp.append(sub)
    return cp

# 갈 수 있는 곳인지 판별해주는 함수
def can_go(x, y, sub_matrix, visited):
    if (x < 0 or y < 0 or x >= n or y >= n):
        return False
    if (sub_matrix[x][y] == 1 or visited[x][y] == 1):
        return False
    else:
        return True

# BFS 수행을 위한 준비
q = deque()

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

# 돌 제거 조합에서 -> 하나씩 뽑으며 -> 따로 복사한 matrix에서 치워보기 -> bfs로 시작점들 이동시켜보기 -> 횟수 저장해서 담기
for r in range(len(pick_rock)):
    rock = pick_rock[r]
    cp_matrix = copy_matrix(matrix)     # matrix 복사해서 cp_matrix에 저장

    # 뽑힌 조합으로 해당 위치에 있는 돌 제거
    for j in range(len(rock)):
        remove_x = rock[j][0]
        remove_y = rock[j][1]
        cp_matrix[remove_x][remove_y] = 0

    # BFS 수행
    move = 0
    visited = [list(0 for _ in range(n)) for _ in range(n)]

    for p in range(len(start_point)):   # 각 시작점을 큐잉해서 탐색 !!!!!
        move += 1
        point = start_point[p]
        q.append([point[0]-1, point[1]-1, move])        # 큐에 각 시작점 값들을 하나씩 append
        visited[point[0]-1][point[1]-1] = 1

    while (q):  # BFS 탐색 시작
        curr = q.popleft()
        x = curr[0]
        y = curr[1]

        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]

            if (can_go(new_x, new_y, cp_matrix, visited)):
                move += 1
                visited[new_x][new_y] = 1
                q.append([new_x, new_y, move])

    ans.append(move)

# print(ans)
print(max(ans))

풀이 및 해설

  • 초반에 헤맸던 부분
    • 이동하면서 → 돌을 치운다 라고 생각해서 어떤 돌을 치워야하는지가 제일 애매했다.
    • 백트랙킹을 통해서 구현할 수 있을 것 같지만 BFS 문제라 BFS로 풀어야 한다고 생각했다.
    • 따라서 완전탐색으로 모두 치워보는 경우들을 다 돌아봐야 한다고 판단 !
  • 따라서 생각한 아이디어
    • 돌의 위치들을 모두 담아보고 → 그 중에서 m개를 뽑는 조합을 구한다면 → 치워볼 돌들의 조합이 만들어짐 (== m개의 돌을 치우는 모든 경우를 찾기)
    • 각 경우에서 시작점 K개에 대해 BFS 탐색 수행
    • 해당 횟수를 ans 리스트에 담아둠
    • 정답은 ans 리스트 중 최댓값
  • 틀렸던 부분
    • 처음에는 각 시작점에서 갈 수 있는 최대의 거리를 찾는다고 생각했는데, 4번 테스트케이스에서 틀리게 되었다.
      틀렸던 테케 44 6 1
      0 1 0 0
      0 1 0 0
      1 0 1 1
      1 1 0 0
      2 4 
      2 1
      1 1
      2 3
      4 4
      3 2
      
      >>> 정답 : 10
      → 여기서 돌 1개 치워서 어떻게 10칸을 이동할 수 있는가?!?! 라고 생각해서 당황
    • 찾아보니 K개의 시작점을 큐잉해서 탐색한 뒤의 갈 수 있는 공간의 크기를 구하는 것이었다 . . .
  • 즉,
    돌 제거 조합에서 → 하나씩 뽑으며 → 따로 복사한 matrix에서 치워보기 → BFS로 시작점들 이동시켜보기 → 횟수 저장해서 담기
    는 맞지만, 시작점을 모두 순서대로 큐에 담은 상태에서 BFS 탐색을 시작하면 됨!!!!
profile
데굴데굴 뚝딱뚝딱 개발기록
post-custom-banner

0개의 댓글