[백준] 경비원 (BFS풀이 + 해설 + 어떻게 생각 했을까)

구현 & BFS & 시뮬레이션 & 수학?

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

2564번: 경비원

 

코드

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

r, c = map(int, input().split())
shop = int(input())


arr = [[0] * (r+1) for _ in range(c+1)]

shop_cordi = []
x, y = 0, 0

def cordi_choice(dic, val, player):
	global x, y

	if player is True:
		if dic == 1:
			x, y = 0, val
		elif dic == 2:
			x, y = c, val
		elif dic == 3:
			x, y = val, 0
		else:
			x, y = val, r

	else:
		if dic == 1:
			shop_cordi.append([0, val])
		elif dic == 2:
			shop_cordi.append([c, val])
		elif dic == 3:
			shop_cordi.append([val ,0])
		else:
			shop_cordi.append([val, r])



def bfs(s, e, arr, shop_cordi):

	queue = deque([[s, e]])
	distance = [[0] * (r+1) for _ in range(c+1)]
	
	distance[s][e] = 1
	dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	# 5, 6, 12

	while queue:
		x, y = queue.popleft()
		for idx in range(4):
			nx = dx[idx][0] + x
			ny = dx[idx][1] + y
			
			if 0<= nx < c+1 and 0 <= ny < r+1 and distance[nx][ny] == 0 and arr[nx][ny] != "x":
				distance[nx][ny] = distance[x][y] + 1
				queue.append([nx, ny])

	total = 0
	for i in shop_cordi:
		f, s = i
		total += distance[f][s]-1
	print(total)


for i in range(shop+1):
	dic, val = map(int, input().split())
    # 주인공 좌표
	if i == shop:
		cordi_choice(dic, val, True)
		for j in range(1, c):
			for k in range(1, r):
				arr[j][k] = "x"	
		bfs(x, y, arr, shop_cordi)
	else:
		cordi_choice(dic, val, False)

 

설명

 최단 거리를 구하는 문제다. 최단 거리 하면 떠오르는 알고리즘이 BFS 그리고 다익스트라 알고리즘이다. 하지만 이 문제에서는 비용이 존재하지 않기 때문에 다익스트라 대신 BFS를 떠올려 풀이를 작성해 보았다. 문제 자체가 읽고 어려웠던 부분은 크게 없었으나 구현력이 부족하여 한번에 솔브하지 못하고 거리를 구하는 구간에서 시간이 오래 걸린 느낌이 있었다. 현재 위에 올려진 코드보다 이전 제출해서 정답을 받지 못했던 코드들과 비교했을 때 '위치를 지정하는 것' 그리고 '점이 사이에 걸쳐 있기 때문에 어디로 위치를 둘지' 이 부분에서 계속 틀리게 되었던 것 같다. 위 코드는 정답을 받은 코드이며 어떤 생각을 했고 풀이를 작성했는지 알아보려고 한다.

 

 해당 문제에서 구하고자 하는 목적은 '동근이의 현재 위치에서부터 각 상점이 위치한 거리들까지의 최단 거리 합'이다. 따라서 우리가 구해야 하는 건 동근이의 위치와, 상점의 위치를 알고 있어야지 동근이의 위치에서부터 거리를 계산할 수 있을 것이다. 이때 주의 해야 하는 것은 예제를 보고 한번 거리를 계산해 보고 어떻게 맵핑할지 생각해야 된다. 중간에 점이 찍혀 있기 때문에 점이 찍혀 있는 양쪽을 기준으로 했을 때 최단거리가 어떻게 나오는지에 따라서 -1을 할지 +1을 해서 점을 찍을지 참 난감했다. 그래서 항상 맵핑의 범위는 입력받은 그대로 두어 문제를 풀어 왔지만 이번 문제 같은 경우 맵의 범위를 r+1, c+1 한 칸씩 늘려 입력받은 범위가 실제 찍히는 범위가 되도록 만들었다. 이렇게 하면 상점 위치를 입력받은 곳에서부터 예제를 그대로 적용해 봤을 때 거리가 정확히 나온다. 동근이의 위치도 상점과 같은 방식으로 찍히게 되므로 마지막에 입력으로 들어오기 때문에 처음에는 shop을 받고 난 다음 따로 처리했지만 그럴 필요가 없을 것 같았고, 한 번에 처리하기 위해서 shop + 1 개만큼 받아 마지막에 들어오는 값은 항상 동근이의 위치기 때문에 그 부분에 왔을 때 따로 처리를 해주었다.  동근이의 위치를 받고 난 이후 문제에서 가장 중요한 점이 존재한다. 그 조건이 바로 아래와 같다.

 

 

직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다.

 

 

 블록 중간이라는 건 가운데를 통과하여 가로질러 갈 수 있는 길이 존재하지 않는다는 것이다. 따라서 어떠한 경우라도 가운데를 가로질러가지 못하기 때문에 즉 이는 다른 말로 겉으로만 이동할 수 있다. 쉽게 생각하면 가운데는 호수고 호수를 감싸고 있는 부분이 도로라고 했을 때 도로 부분만 갈 수 있다는 것이다. 그렇기 때문에 예제에서도 '시계방향', '반시계방향'을 예로 들어주고 있고 이를 통해 가운데 부분 전체는 가지 못한다는 걸 추론할 수 있다.

 

 겉 부분만 지나가기 위해서 이제 생각해야 하는 건 어떻게 겉 부분만 가게 할 것인지다. 처음에 한 방향으로만 쭉 가게 만들어야 할지 동 서 남 북 각각 두 방향씩 진행하게 되니 두 번씩 돌려야 할지 고민을 했었는데 BFS를 사용하는 목적을 다시금 상기하며 고민해 본 결과 가운데 부분이 호수라고 했으니 가운데 부분만 가지 못하도록 우선적으로 막아둔 뒤 이후 진행할 곳들은 방문하지 않은 지점들만 가면 된다. 이렇게 되면 동 서 남 북 각각 따로 구현하는 것 없이 한 번에 구해지기 때문이다. 만약 이를 하지 않는다면 동근이의 위치가 남쪽에 있다고 가정했을 때 서쪽 방향과 동쪽 방향으로 이동하게 되며 가장 끝에 도달했을 때 다시 위로 위치를 돌려야 한다. 마찬가지로 다른 위치에 있을 때도 이와 같이 생각해 보면 상당히 많은 조건문이 생성된다. 따라서 가운데 부분을 막는 방법이 곧 상 하 좌 우 탐색하기에 가장 최적의 조건이 된다. 단순히 생각해 본다면 방문한 곳은 가지 못하며, 가운데 부분은 가지 못하니 현재 부분에서 가운데 부분 쪽으로 가려고 하면 가지 못한다. 그럼 이전 경로를 이미 방문하면서 왔기 때문에 범위가 벗어나는 곳, 방문한 곳, 가운데로 가려고 하는 곳 이들을 제외한다면 4방향 중 딱 한 방향만이 남게 된다. 그럼 그 방향이 곧 범위가 벗어나지 않으면서 그리고 방문하지도 않았고 가운데도 아닌 곳이 된다. 다시 말해 방문이 가능한 지점이 된다라는 뜻이다. 

 

 BFS를 진행하면서 상점에 도달했을 때의 값들을 살펴보아야 한다. 처음에 cordi_choice 함수를 통해서 상점의 위치들을 따로 리스트에 만들어 두었고 BFS가 진행되면서 얼마큼 지나왔는지의 대한 값을 남기기 때문에 이후 그 남겨진 값을 통해 최단 거리들의 합을 구할 수 있다. 이때 왜 그렇게 방문하는 게 최단거리가 되느냐 하면 BFS는 항상 최단 경로를 보장하기 때문이다. 앞서 다른 문제에서도 언급해 보며 왜 BFS가 최단경로를 보장하는지에 대해서 작성해 본 적이 있다. 짧게 언급하고 가면 도착하는 목적지가 아닌 곳들은 도착하는 지점보다 가지를 더 많이 뻗게 된다. 그렇기 때문에 도착하는 그 지점에 대해서 항상 최단 경로를 보장하게 되는 것이다. 

 

 이후 BFS가 끝났다면 갈 수 있는 모든 곳을 갔기 때문에 그중에 당연히 상점으로 지정된 곳도 지나갔을 것이다. 그럼 이제 리스트에 만들어 두었던 상점의 값들을 하나씩 가져와 맵에 저장되어 있는 값을 이용해 최종 최단 거리들을 누적해서 합산하면 된다. 초기 거리를 1로 설정했기 때문에 값들이 하나씩 커지게 되어 -1을 조정하여 값을 구했다. 물론 BFS과정에서 shop부분을 만나게 된다면 바로 합산을 해주어도 되겠지만, 이전 코드들에서 distance의 거리 구하는 게 꼬였던 탓인지 이번엔 확실히 하기 위해서 마지막에 구해주었다.