흙금이네 블로그

아이디어 BFS로 한 C칸에서 다른 C칸까지의 각 칸에 방문하기 위해 설치해야 할 최소 거울 개수를 구해 나간다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): W, H = map(int, input().split()) board = [[*input().rstrip()] for _ in range(H)] visited = [[-1]*W for _ in range(H)] K = max(W, H) points = [] for r in range(H): for c in range(W): if board[r][c] == 'C': points.append((r, c)) stack =..

아이디어 상근이가 있는 감옥 외부와 두 죄수가 있는 칸에서 각각 0-1 BFS로 탐색한다. 모든 칸에 대해 열어야 하는 최소 문 개수들을 구한 후, 세 사람이 만나는 칸의 문 개수 합의 최솟값을 구한다. 풀이 import sys from collections import deque input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): def bfs(x, y): visited = [[-1]*w for _ in range(h)] visited[x][y] = 0 queue = deque([(x, y, 0)]) while queue: r, c, cnt = queue.popleft() for dr, dc in de..

아이디어 막대기를 맞아 미네랄이 파괴된 칸을 기준으로 주변을 BFS하여 바닥에 닿아 있지 않은 클러스터들을 이동시킨다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): def throw(i, j): visited = [[0]*C for _ in range(R)] for di, dj in delta: ni, nj = i+di, j+dj if R > ni >= 0 and C > nj >= 0: if board[ni][nj] == 'x' and visited[ni][nj] == 0: visited[ni][nj] = 1 bottom = [-1]*C queue = [(ni, nj)] ..