[백준 1931번 알고리즘] 회의실 배정 파이썬 풀이

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

백준 1931번 bfs

저번 시간에 이어 bfs문제를 하나 더 풀어보려고 합니다. 개인적으로 이 문제가 더 쉽게 느껴졌는데요.

우리가 고려해야할건 2가지입니다.

 

Q1. 2까지의 최단거리...?

바로 bfs를 떠올리셔야합니다. 

bfs에 대해 잘모르신다면 아래 링크를 통해 학습해주시길 권장드립니다.

https://coldmans.tistory.com/1

BFS를 활용한 목표 지점까지의 거리 구하기

BFS(Breadth-First Search)를 사용하여 2차원 지도에서 특정 목표 지점까지의 거리를 구하는 문제를 해결해보겠습니다. 이 문제는 주어진 지도를 기반으로 각 지점에서 목표 지점까지의 거리를 계산하는 것입니다. 지도는 오직 가로와 세로로만 움직일 수 있으며, 목표 지점은 한 군데만 존재합니다.

 

그럼 결국 2지점에서 모든 점까지의 최단거리를 구하는 문제랑 다름이 없다고 보시면 됩니다....!!!!!!

 

Q2. 음,,,,, 1인데 접근 못하는건 어떻게하죠...?

간단합니다. visited배열을 만들어 bfs를 진행한 후 완전탐색을 통해 1을 찾고 visited배열에서 방문하지 않은걸로 나온다면

-1로 바꿔준뒤 출력하면 끝입니다.

 

import sys
from collections import deque
input = sys.stdin.readline

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

graph = [[int(x) for x in input().strip().split()] for _ in range(n)]
visited = [[-1 for _ in range(m)] for _ in range(n)]

q = deque()
for y in range(n):
    for x in range(m):
        if graph[y][x] == 2:
                q.append((y,x))
                graph[y][x] = 0
                visited[y][x] = 1
                break

while q:
    y,x = q.popleft()
    for dy, dx in ((1,0),(0,1),(-1,0),(0,-1)):
         ga = x + dx
         se = y + dy
         if (0<= ga <m) and (0 <= se < n) and (graph[se][ga] == 1) and (visited[se][ga] == -1):
              graph[se][ga] += graph[y][x]
              visited[se][ga] = 1
              q.append((se,ga))

for y in range(n):
    for x in range(m):
        if (graph[y][x] == 1) and (visited[y][x] == -1):
            graph[y][x] = -1
        print(graph[y][x], end = " ")
    print()

코드 설명

1. 입력 받기: sys.stdin.readline을 사용하여 입력을 받습니다. n과 m을 입력받고, 그에 따라 지도를 2차원 리스트로 저장합니다.
2. 초기화: 방문 여부를 확인하기 위한 visited 리스트를 초기화합니다. 모든 값은 -1로 초기화합니다.
3. 목표 지점 찾기: 이중 루프를 돌며 목표 지점(값이 2인 지점)을 찾습니다. 찾으면 큐에 추가하고, 해당 지점을 0으로 바꾸고 방문 처리합니다.
4. BFS 알고리즘: 큐를 사용하여 BFS를 수행합니다. 현재 지점에서 상하좌우로 이동하며 갈 수 있는 지점(값이 1인 지점)을 찾고, 그 지점을 큐에 추가합니다.
5. 결과 출력: BFS가 끝난 후, 지도 전체를 돌며 방문하지 못한 지점(값이 1이지만 방문되지 않은 지점)은 -1로 바꾸고, 모든 지점을 출력합니다.

이 코드를 통해 각 지점에서 목표 지점까지의 거리를 쉽게 구할 수 있습니다. BFS 알고리즘을 사용하여 효율적으로 문제를 해결할 수 있습니다.