1. 문제 - 백준 4991 로봇 청소기
https://www.acmicpc.net/problem/4991
💡알고리즘
1️⃣ BFS
로봇에서 각 더러운 칸을 방문할 때, 더러운 칸에서 더러운 칸을 방문할 때 소요되는 최단거리를 계산할때 사용한다.
2️⃣ 순열
로봇청소기가 현재 위치에서 어떤 더러운 칸을 먼저 방문할지에 따라서 모든 더러운 칸을 청소하는 데 있어 매번 이동 횟수의 최솟값이 달라지기 때문에, permutations(순열) 을 통해 완전탐색하며 이동 횟수의 최소값을 비교해야한다.
✍🏻 막힌, 헷갈린 부분
로봇은 같은 칸을 여러 번 방문할 수 있다.
--> visited로 방문처리를 하지 않으면 BFS가 매번 모든 인접한 칸을 그래프 탐색하는거 아닌가?
--> BFS는 로봇청소기가 각 더러운 칸을 방문할 때의 최단 거리를 계산하는 것이므로, 최단 거리를 계산할 때 방문했던 칸을 또 방문한다는 문장에서 이미 최단거리가 아니게 됨. 즉 이때는 원래의 BFS 대로 visited를 통해 방문 여부를 체크하는것이 맞음.
--> 같은 칸을 여러번 방문할 수 있다는 것은, 더러운 칸과 칸 사이를 이동할 때 여러 번 방문할 수 있어 제약이 없다는 의미로 해석
더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값
--> 이부분은 어떻게 구할 수 있을지 아얘 감이 안왔음
--> 어떤 더러운 칸을 먼저 방문할지에 따라서 더러운 칸들을 이동하는 데 소요되는 이동횟수가 달라지므로, 순열을 통해 완전탐색하여 비교한다. (w와 h의 범위가 20이므로 시간제한에 걸리지 않음)
✅ 풀이
더러운 칸을 간단하게 먼지라고 하겠습니다 ..!
from collections import deque
from itertools import permutations
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(start_x, start_y):
q = deque([(start_x, start_y)])
visited[start_x][start_y] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<h and 0<=ny<w and board[nx][ny] != "x" and visited[nx][ny] == -1:
q.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
break
board = []
robot_x, robot_y = 0, 0
dirties = []
for i in range(h):
board.append(list(input()))
for j in range(w):
if board[i][j] == "o":
robot_x, robot_y = i, j
if board[i][j] == "*":
dirties.append((i, j))
# 1) 로봇과 각 더러운 칸 사이의 최단 거리 계산
visited = [[-1] * w for _ in range(h)]
bfs(robot_x, robot_y)
robot_to_dust_destinations = [0] * len(dirties)
# 이후 첫번째로 방문할 먼지를 순열로 만들기 위해 사용할 로봇과 먼지 사이의 최단거리 배열
flag = False
for i, (x, y) in enumerate(dirties):
if visited[x][y] == -1:
flag = True
break
else: # 로봇-더러운 칸 사이의 최단거리 배열을 최단거리로 갱신
robot_to_dust_destinations[i] = visited[x][y]
if flag: # 방문할 수 없는 더러운 칸이 존재하므로 -1 출력 후 종료
print(-1)
continue
# 2) 더러운 칸과 더러운칸 사이의 최단거리 계산
dist = [[0] * len(dirties) for _ in range(len(dirties))]
for i in range(len(dirties)):
visited = [[-1] * w for _ in range(h)]
bfs(dirties[i][0], dirties[i][1]) # 현재 더러운 칸을 시작점으로 하여 다른 각 칸을 이동하기 위해 소요되는 최단 거리 계산
for j in range(len(dirties)):
if i == j:
continue
if not dist[i][j] or not dist[j][i]:
dist[i][j] = visited[dirties[j][0]][dirties[j][1]]
dist[j][i] = dist[i][j]
# 3) 순열을 통해 방문할 더러운 칸 순서들을 정하여 이동 횟수의 최소값 갱신
answer = int(1e9)
for perm in permutations(range(len(dirties))):
start = perm[0]
_sum = robot_to_dust_destinations[start]
for i in range(1, len(perm)):
end = perm[i]
_sum += dist[start][end]
start = end # start를 그 다음 방문한 더러운 칸으로 바꿔줘야함 (방문한 더러운 칸과 그 다음 방문할 더러운 칸 사이의 거리를 계산하는 것이므로)
answer = min(answer, _sum)
print(answer)
1) 로봇과 각 더러운 칸사이의 최단 거리 계산
- 어떤 먼지를 먼저 방문하느냐에 따라서 더러운 칸을 모두 깨끗한 칸으로 만드는 데 필요한 이동 횟수의 최소값이 달라진다.
- 로봇에서 먼저 방문할 먼지 순서는 이후 순열을 통해서 순서를 정한다고 했을 때
먼저 로봇이 각 먼지를 이동하는 데 소요되는 최단 거리 계산이 필요할 것이다. - BFS를 통해 로봇에서 각 먼지까지 이동하는 데 드는 소요되는 시간을 계산하여 robot_to_dust_destinations 배열에 저장한다.
- 만약에 이 과정에서 방문할 수 없는 먼지가 있다면 (visited[x][y] == -1) -1을 출력하고 현재 단계의 프로그램을 종료한다.
# 1) 로봇과 각 먼지사이의 최단 거리 계산
visited = [[-1] * w for _ in range(h)] # BFS 이후 로봇에서 각 먼지까지의 최단거리가 적힐 배열
bfs(robot_x, robot_y)
robot_to_dust_destinations = [0] * len(dirties)
# 이후 첫번째로 방문할 먼지를 순열로 만들기 위해 사용할 로봇과 먼지 사이의 최단거리 배열
flag = False
for i, (x, y) in enumerate(dirties):
if visited[x][y] == -1:
flag = True
break
else: # 로봇-먼지사이의 최단거리 배열을 최단거리로 갱신
robot_to_dust_destinations[i] = visited[x][y]
if flag: # 방문할 수 없는 더러운 칸이 존재하므로 -1 출력 후 종료
print(-1)
continue
2) 먼지와 먼지 사이의 최단거리를 계산한다.
- 로봇에서 먼저 방문할 먼지를 정했다면, 먼지에서 다른 먼지로 이동할 최단 거리를 계산해야할 것이다.
- 마찬가지로 각 먼지들을 시작점으로 잡고 다른 먼지들과의 최단거리를 BFS를 통해 계산하면 된다.
- dist[i][j]는 i에서 j까지 방문했을 때의 최단거리를 의미하고, dist[j][i]는 거리이기 때문에 값이 동일하다.
dist = [[0] * len(dirties) for _ in range(len(dirties))]
for i in range(len(dirties)):
visited = [[-1] * w for _ in range(h)]
bfs(dirties[i][0], dirties[i][1]) # 현재 먼지를 시작점으로 하여 다른 각 먼지를 이동하기 위해 소요되는 최단 거리 계산
for j in range(len(dirties)):
if i == j:
continue
if not dist[i][j] or not dist[j][i]:
dist[i][j] = visited[dirties[j][0]][dirties[j][1]]
dist[j][i] = dist[i][j]
3) 순열을 통해 방문할 더러운 칸 순서들을 정하고, 완전 탐색을 통해 필요한 이동 횟수의 최소값을 갱신한다.
- permutations를 통해 방문할 더러운 칸들의 순서를 정한다. 여기서는 더러운 칸에 인덱스로 번호를 붙인다고 했을 때, range(len(dirties))로 하면 [0, 1, 2], [0, 2, 1] ... 등의 결과가 나올것이다.
- start = perm[0] 은 로봇이 가장 먼저 방문할 먼지 순서이다.
- _sum 에는 모든 먼지들을 방문할 때 소요되는 이동 횟수의 총합인데, 처음에는 로봇이 첫번째 먼지를 방문하기 위해 소요되는 거리일 것이다. 따라서 _sum = robot_to_dust_destinations[start]
- 이후 순서에 따라 먼지와 먼지 간의 거리를 더해주고, 총합의 최소값을 갱신한다.
# 3) 순열을 통해 방문할 먼지 순서들을 정하여 이동 횟수의 최소값 갱신
answer = int(1e9)
for perm in permutations(range(len(dirties))):
start = perm[0]
_sum = robot_to_dust_destinations[start]
for i in range(1, len(perm)):
end = perm[i]
_sum += dist[start][end]
start = end # start를 그 다음 방문한 먼지로 바꿔줘야함 (방문한 먼지와 그 다음 방문할 먼지 사이의 거리를 계산하는 것이므로)
answer = min(answer, _sum)
print(answer)
2. 문제 - 백준 19637 IF문 좀 대신 써줘
https://www.acmicpc.net/problem/19637
💡알고리즘 - 이분 탐색
- 입력받는 수마다 범위를 찾아 그에 해당하는 칭호를 찾는 문제이다. 근데 칭호의 갯수가 무려 10^5이고 칭호를 주어야하는 캐릭터의 갯수가 10^5이다..! 그말은 즉슨 O(n^2)로 탐색하는 방법은 시간초과로 통과하지 못할 확률이 높다.
- 칭호가 오름차순으로 정렬되어 있고, 탐색의 시간 복잡도를 줄여야하고, 범위에 해당하는 칭호를 구하는 부분에서 이분탐색임을 알 수 있다.
✅ 풀이
import sys
input = sys.stdin.readline
n, m = map(int, input().rstrip().split())
levels = []
for _ in range(n): # 10^5
name, limit = input().rstrip().split()
levels.append((name, int(limit)))
for _ in range(m):
level = int(input())
left = 0
right = n-1
answer = 0
while left <= right:
mid = (left + right) // 2
if level > levels[mid][1]:
left = mid + 1
else:
right = mid - 1
answer = mid
print(levels[answer][0])
- 이때 주의할 점은 입력이 시간이 많이 소요되는 편인데, 그냥 Input()으로 입력받으면 칭호의 갯수와 캐릭터의 갯수가 모두 10^5이기 때문에 시간초과가 난다.
- input의 시간을 줄여주는 sys.stdin.readline을 사용해서 입력받을 때의 시간복잡도를 줄이자.
'⚙️ 알고리즘 > 문제풀이' 카테고리의 다른 글
| [Python] 백준 16434 드래곤 앤 던전 (0) | 2025.08.15 |
|---|---|
| [Python] 백준 1347 미로만들기 (0) | 2025.08.08 |
| [Python] 프로그래머스 광고 삽입 (0) | 2025.08.05 |
| [Python] 백준 19238 스타트 택시 (0) | 2025.08.04 |
| [Python] 백준 2504 괄호의 값 (0) | 2025.08.04 |