BFS에서 최단 경로 문제를 풀 땐 또는 방향 순서를 안정된 기준(예: 시계 방향) 으로 맞춰줘야 함
from collections import deque
case = int(input())
ans = []
for _ in range(case):
n = int(input())
graph = []
for _ in range(n):
row = [0] * n
graph.append(row)
distance = []
for _ in range(n):
row = [0] * n
distance.append(row)
start_x, start_y = map(int, input().split())
goal_x, goal_y = map(int, input().split())
# 시계방향대로 이동 할 수 있는 수를 둠, BFS에서는 방향 순서를 신경써야 함
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]
def BFS(y, x):
queue = deque()
queue.append((y, x))
graph[y][x] = 1
while queue:
y, x = queue.popleft()
if y == goal_y and x == goal_x:
return distance[y][x]
for i in range(len(dx)):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and graph[ny][nx] == 0:
distance[ny][nx] = distance[y][x] + 1
queue.append((ny, nx))
graph[ny][nx] = 1
ans.append(BFS(start_y, start_x))
for i in ans:
print(i)
from collections import deque
f, s, g, u, d = map(int, input().split()) # 건물의 총 수, 현재 위치, 회사 위치, 위로 u층, 아래로 d층
distance = [0] * (f + 1)
visited = [False] * (f + 1)
def BFS(s):
queue = deque()
queue.append(s)
visited[s] = True
while queue:
current = queue.popleft()
if current == g:
return distance[current]
for next in (current + u, current - d):
if 0 < next <= f and not visited[next]:
queue.append(next)
visited[next] = True
distance[next] = distance[current] + 1
return "use the stairs"
print(BFS(s))
from collections import deque
n, m = map(int, input().split()) # 세로 크기(높이), 가로 크기
graph = []
for _ in range(n):
row = list(map(int, input().split()))
graph.append(row)
# 상하좌우 세팅
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def BFS(y, x):
queue = deque()
queue.append((y, x))
graph[y][x] = 0
count = 1
while queue:
y, x = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= m or ny >= n:
continue
if graph[ny][nx] == 0:
continue
if graph[ny][nx] == 1:
queue.append((ny, nx))
graph[ny][nx] = 0
count = count + 1
return count
ans = []
art = 0
for y in range(n):
for x in range(m):
if graph[y][x] == 1:
art = art + 1
ans.append(BFS(y, x))
print(art)
if art == 0:
print(0)
else:
print(max(ans))
하지만 총 달걀의 수를 초과해서 구매할 수 없기 때문에 min함수를 사용하여 고객과 달걀의 수 중에서 최소값을 고른다
n, m = map(int, input().split()) # 달걀의 개수, 손님의 수
consumer = [] # 각 손님별로 구매할 수 있는 가격의 최대값
for _ in range(m):
price = int(input())
consumer.append(price)
consumer.sort()
idx = 0
ans_price = 0
ans_egg_price = 0
for p in consumer:
count = min(n, len(consumer[idx:]))
idx = idx + 1
max_price = count * p
if ans_price < max_price:
ans_price = max_price
ans_egg_price = p
print(ans_egg_price, ans_price)
person = {"name": "Alice", "age": 25}
print("name" in person) # ✅ True
print("gender" in person) # ❌ False
정답
알파벳도 sort(), sorted() 함수로 오름차순, 내림차순 정렬이 가능함
n = int(input())
book = {}
for _ in range(n):
title = input()
# 이미 딕셔너리에 값이 있다면 1 증가, 아니라면 값 1 넣기
if title in book:
book[title] = book[title] + 1
else:
book[title] = 1
# 딕셔너리의 값들 중, 가장 큰 수 추출
best = max(book.values())
ans = []
# 딕셔너리를 탐색하며 가장 큰 수와 같은 값을 가진 책 이름 리스트에 추가
for key, value in book.items():
if value == best:
ans.append(key)
# 오름차순으로 알파벳 정렬
a = sorted(ans)
print(a[0])
from collections import deque
n, k = map(int, input().split())
def BFS(n, k):
# 최대 점의 길이 + 1 (리스트는 0부터 시작하므로)
max_value = 100001
# 방문을 체크할 리스트
visited = [False] * max_value
# 최초 시작지점 (수빈이의 위치)부터의 거리를 담는 리스트
distance = [0] * max_value
queue = deque()
queue.append(n)
visited[n] = True
while queue:
current = queue.popleft()
# 현재 위치가 동생의 지점이라면, 수빈이의 지점부터 동생의 지점까지의 거리 반환
if current == k:
return distance[current]
# 현재 위치가 동생의 지점이 아니라면, 수빈이가 갈 수 있는 경우의 수 걷기, 뛰기를 적용하여 조건에 부합한다면 큐에 넣기
for next in (current - 1, current + 1, current * 2):
# 0이상, 100000이하이고 방문하지 않았다면
if next >= 0 and next < max_value and not visited[next]:
queue.append(next)
visited[next] = True
distance[next] = distance[current] + 1
print(BFS(n, k))
from collections import deque
t = int(input())
ans = []
for i in range(t):
m, n, c = map(int, input().split()) # 배추밭 가로길이, 세로길이, 배추가 심어져 있는 개수
# 배추밭 세팅
graph = []
for _ in range(n):
row = [0] * m
graph.append(row)
for _ in range(c):
x, y = map(int, input().split())
graph[y][x] = 1
# 상하좌우 세팅
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def BFS(y, x):
queue = deque()
queue.append((y, x))
graph[y][x] = 0
while queue:
y, x = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= m or ny >= n:
continue
if graph[ny][nx] == 0:
continue
if graph[ny][nx] == 1:
queue.append((ny, nx))
graph[ny][nx] = 0
count = 0
for y in range(n):
for x in range(m):
if graph[y][x] == 1:
count = count + 1
BFS(y, x)
ans.append(count)
for i in ans:
print(i)
아무런 땅이 물에 젖지 않는 경우도 포함해야 하기 때문에 비가 오는 경우를 0부터 넣어서 체크해야 함 (1부터 시작하면 1이하의 땅은 젖기 때문에)
from collections import deque
n = int(input()) # n * n 지도
# 지도 세팅
graph = []
for _ in range(n):
row = input()
row_list = list(map(int, row.split()))
graph.append(row_list)
# 상하좌우 세팅
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def BFS(x, y, g):
queue = deque()
queue.append((x, y))
g[x][y] = 0
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= n:
continue
if g[nx][ny] == 0:
continue
if g[nx][ny] != 0:
queue.append((nx, ny))
g[nx][ny] = 0
# 0부터 100까지 높이로 물에 잠긴다고 가정했을 때 뮬애 안 잠기는 가장 큰 수가 정답 (아무 지역도 물에 안 잠기는 경우도 있으므로 0부터 시작해야 함)
ans = []
for i in range(0, 101):
area = 0
# 그래프 세팅
g = [row[:] for row in graph]
for x in range(n):
for y in range(n):
if g[x][y] <= i:
g[x][y] = 0
for x in range(n):
for y in range(n):
if g[x][y] != 0:
area = area + 1
BFS(x, y, g)
ans.append(area)
print(max(ans))
