JUNGLE 240327 (W01)
KRAFTON JUNGLE Week 01
1. BOJ Issue
10971. 외판원 순회 2
처음에 감이 안잡혀서 안전 영역보다 체감상 더 어려웠음
import sys
input = sys.stdin.readline
N = int(input())
Map = [list(map(int, input().split())) for _ in range(N)]
visited = [False] * N # 방문 체크
min_cost = float('inf') # 최소 비용을 업데이트 할 것이므로 무한으로 초기화
min_cost: 최소 비용 업데이트를 위해 무한으로 초기화 해준다.visited: 방문 체크를 위해 1차원 배열을 선언한다.
def visit(start, next, cost, visited):
global min_cost
if len(visited) == N: # 순회가 끝나면,
tmp = Map[next][start] # 다시 시작 노드로 돌아가는 비용 추가
if tmp != 0: # 간선이 존재할 때
min_cost = min(min_cost, cost + tmp) # 최소 비용 업데이트
return
Map[next][start]: 순회가 끝나면 다시 시작 노드로 돌아가는 비용을 추가 (next->start)min_cost에 최소 비용을 계속해서 업데이트
for i in range(N):
tmp = Map[next][i] # 현재 노드에서 다음 노드로의 비용
if tmp != 0 and i not in visited and cost < min_cost:
visited.append(i) # 방문 체크
visit(start, i, cost + tmp, visited) # 재귀적으로 탐색
visited.remove(i) # 백트래킹
for i in range(N):
visit(i, i, 0, [i])
print(min_cost)
- 재귀적으로 탐색 후 백트래킹 방식으로 가능한 경우의 수를 계산
- ✔ 백트래킹 (Backtracking)
- 가능한 모든 해를 탐색하면서 특정 조건을 만족하는 해를 찾는 기법
- 주어진 조건에 맞지 않는 경우에는 그 부분을 더 이상 탐색하지 않고 즉시 이전 단계로 돌아감
2468. 안전 영역
연구소 문제랑 상당히 비슷하다.
from collections import deque
import sys
input = sys.stdin.readline
d = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 상하좌우 방향
def bfs(depth, visited):
count = 0
for i in range(N):
for j in range(N):
if not visited[i][j] and Map[i][j] > depth: # 방문한 적이 없고 안전 영역이라면,
count += 1
queue = deque([(i, j)]) # 큐에 현재 위치 삽입
visited[i][j] = True # & 방문 처리
while queue: # 큐에 있는 위치들에 대해
x, y = queue.popleft()
for k in range(4): # 상하좌우 좌표 체크
nx = x + d[k][0]
ny = y + d[k][1]
# 만약, 방문한 적이 없고 지도를 벗어나지 않으면서 안전 영역이라면,
if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] is False and Map[nx][ny] > depth:
queue.append((nx, ny)) # 큐에 좌표 삽입
visited[nx][ny] = True # & 방문 처리
return count
N = int(input())
Map = [list(map(int, input().split())) for _ in range(N)]
max_count = 0
for depth in range(101):
visited = [[False] * N for _ in range(N)]
max_count = max(max_count, bfs(depth, visited))
print(max_count)
bfs함수에서 물의 깊이depth와 방문 여부visited를 인수로 받아온다.for문으로 물의 수위에 대해 안전 영억의 개수를 세고 각각의 안전 영역 개수를 계산한 다음,- 최댓값을 도출하기 위해 계속해서
max_count를 업데이트 한다.
8983. 사냥꾼
import sys
input = sys.stdin.readline
M, N, L = map(int, input().split())
shots = list(map(int, input().split()))
animals = []
for i in range(N):
a, b = map(int, input().split())
animals.append((a, b))
- 사대 위치를 기준으로 잡을 수 있는 동물을 카운트하는 것보다 동물을 기준으로 사대의 개수를 세는 것이 효율적
- 동물들의 좌표를 리스트에 삽입 후 각각의 동물 좌표에 대해 사정거리를 계산한다.
count = 0
shots.sort()
for a, b in animals:
if b > L:
continue
Min = a + b - L
Max = a - b + L
- 이 문제에서 거리를 계산하는 방식은
|x - a| + b(x는 사대의 위치,(a, b)는 동물의 위치)- 즉, 동물을 잡기 위해서는
|x - a| + b < L이어야 한다.- 이를 활용해 사대 좌표의 범위를 구하면,
Min = a + b - L,Max = a - b + L이 된다.
start = 0
end = len(shots) - 1
while start <= end:
mid = (start + end) // 2
if Min <= shots[mid] <= Max:
count += 1
break
elif shots[mid] < Max:
start = mid + 1
else:
end = mid - 1
print(count)
- 동물을 기준으로 잡을 수 있는 사대의 위치를 계산하고 이분 탐색으로 사대의 범위를 줄여나가면 끝
- (선형 탐색으로도 구현은 가능하지만, 시간이 매우 오래 걸리고 채점 결과가 60점이 나옴)
