문제 1. 개미와 진딧물

• 구현 / 완전 탐색 / 좌표 추출
• 맨해튼 거리로 계산하면 빠르게 할 수 있음

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

def bfs(house, ant, N, M):
	dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
	result = 0
	
	while (ant):
		visited = [[0] * N for _ in range(N)]
		queue = deque([ant.popleft()])
		
		while queue:
			x, y = queue.popleft()
			
			if M <= visited[x][y]:
				continue
				
			for k in range(4):
				nx, ny = x + dx[k], y + dy[k]
				if 0 <= nx < N and 0 <= ny < N:
					if visited[nx][ny] == 0:
						visited[nx][ny] = visited[x][y] + 1
						queue.append((nx, ny))
					if house[nx][ny] == 2:
						result += 1
						queue.clear()
						break
		
	print(result)

N, M = map(int, input().split())
house = []
ant = deque()
for i in range(N):
	house.append(list(map(int, input().split())))
	ant.extend([(i, j) for j in range(N) if house[i][j] == 1])

bfs(house, ant, N, M)

# 답지
def manhattan(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

n, k = map(int, input().split())
list_1 = list()
list_2 = list()
for i in range(n):
    tmp = list(map(int, input().split()))
    for s in range(n):
        if tmp[s] == 1:
            list_1.append([i, s])
        elif tmp[s] == 2:
            list_2.append([i, s])

cnt = 0
for pos1 in list_1:
    idx = 0
    while True:
        if idx == len(list_2):
            break
        pos2 = list_2[idx]
        if manhattan(pos1, pos2) <= k:
            cnt += 1
            break
        else:
            idx += 1
print(cnt)

문제 2. 모래섬

• 2차원 배열 / 시뮬레이션 / 그래프 탐색

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

def check_bridge_bfs(visited, start, N, M):
	dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
	queue = deque([start])
	
	while queue:
			x, y = queue.popleft()
			for k in range(4):
				nx, ny = x + dx[k], y + dy[k]
				if 0 <= nx < N and 0 <= ny < M:
					if visited[nx][ny] == 1:
						visited[nx][ny] = 0
						queue.append((nx, ny))
	
	return 1

def bfs(sand, water, N, M):
	dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
	result = 0

	while water:
		
		queue = deque(copy.deepcopy(water))
		water = deque()
		while queue:
			x, y = queue.popleft()
				
			for k in range(4):
				nx, ny = x + dx[k], y + dy[k]
				if 0 <= nx < N and 0 <= ny < M:
					if sand[nx][ny] == 1:
						sand[nx][ny] = 0
						water.append((nx, ny))
		result += 1
		
		visited = copy.deepcopy(sand)
		cnt = 0
		for i in range(N):
			for j in range(M):
				if visited[i][j] == 1:
					visited[i][j] = 0
					cnt += check_bridge_bfs(visited, (i, j), N, M)

		if 1 < cnt:
			return result
	
	return -1

N, M = map(int, input().split())
sand = []
water = []
for i in range(N):
	sand.append(list(map(int, input().split())))
	water.extend([(i, j) for j in range(M) if sand[i][j] == 0])

print(bfs(sand, water, N, M))

문제 3. 수 이어 붙이기

• 완전 탐색 / 순열 → N의 제한이 8로 매우 작다는 점
• 가능한 모든 배치 방법을 시도해보는 O(N * N!) 풀이가 여유롭게 통과

10 이상 99 이하 서로 다른 수 N개

from itertools import permutations

N = int(input())
A = list(map(int, input().split()))
# A.sort()

ans = 1e18
for order in permutations(A, N):
    cur = order[0]
    for i in range(1, N):
        if cur % 10 == order[i] // 10:
            cur = cur * 10 + order[i] % 10
        else:
            cur = cur * 100 + order[i]
    ans = min(ans, cur)

print(ans)

이어붙이는데 일의 자리 숫자와 십의 자리 숫자가 같으면 겹쳐서 이어붙임

제일 작은 수를 찾고, 모든 카드를 다 사용해야 함

1 ≤ N ≤ 8