Today I Learned

오늘도 토요일에 있을 테스트를 대비하기 위해 파이썬으로 코테 연습을 했다.

개미 집합의 지름

개미 집합의 지름

수직선 위에 개미 n마리가 있다. 임의의 두 개미 사이중 가장 긴 거리가 d이하가 되게 개미를 제거하려 한다. 제거되는 개미의 최소 숫자를 반환해라.

입력
11 5
10 11 12 13 14 15 16 17 18 19 20
출력
5

코드 및 문제 풀이

• 슬라이딩 윈도우를 사용해서 창의 크기를 구한 뒤 n에서 빼주면 되는 문제다.

• 왼쪽 index를 저장하는 변수와 최대 창의 크기 변수를 할당해준다. range(n)의 범위에서 개미 지름이 d보다 크면 l을 한칸 땡기고 창 크기가 max가 되는 구간의 크기를 저장해둔다.

• 창의 크기가 최대가 되어야 제거되는 개미가 최소가 되기 때문이다. 마지막에 차이를 반환하면 완료!

n, d = map(int, input().split())
ants = list(map(int, input().split()))
ants.sort()

l = 0
max_len = 0

for r in range(n):
	while ants[r] - ants[l] > d:
		l += 1
	max_len = max(max_len, r-l+1)

print(n-max_len)

발전기

발전기

한 변의 길이가 n인 정사각형 마을 m이 있다. 이 마을의 각 집은 0 또는 1이며 1이면 집이있고 0이면 아무것도 없다. 마을에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나 상하좌우 인접한 집에 전기가 들어오면 된다. 모든 집에 전기를 공급하기 위해서 설치해야하는 발전기의 최소 개수를 구해라.

입력
4
1 1 1 1
0 0 0 1
1 1 1 1
1 0 0 1
출력
1

코드 및 풀이과정

• bfs로 풀면 쉽게 풀린다. 파이썬으로 bfs를 구현해보기는 처음이다.

• deque을 이용해 큐를 만들고 popleft(), append() 함수를 사용했다.
  방향은 자바때와 마찬가지로 direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]로 만들고 for dx, dy in direction:으로 진행한다.

• 마을의 좌표는 m = [list(map(int, input().split())) for _ in range(n)] 이렇게 2차원 리스트로 받는다.

• 방문기록용 2차원 boolean 리스트는 visited = [[False] * n for _ in range(n)] 이렇게 만든다.

from collections import deque

def bfs(start_x, start_y, m, visited, n):
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque([(start_x, start_y)])
    visited[start_x][start_y] = True
    
    while q:
        x, y = q.popleft()
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and m[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))


n = int(input())
m = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
count = 0

for x in range(n):
		for y in range(n):
				if m[x][y] == 1 and not visited[x][y]:
						bfs(x, y, m, visited, n)
						count += 1

print(count)