[백준][1303] 전쟁 - 전투
BFS (너비우선탐색)
이 문제에 대해 양심 고백을 하자면,
바로 밑의 '미로 탐색 (2178)' 문제를 풀다가 실패하고, 구글링으로 정답 코드의 알고리즘들을 봤다.
그래서 원리 자체는 어떤 거구나 살짝 감을 잡은 상태에서, 미로 탐색은 나중에 다시 풀어보려는 생각으로 다음 문제를 건드렸는데...
이 문제도 BFS를 사용하는 원리가 똑같았다.
그래서 이 문제는 온전히 혼자 머리에서 나왔다고 하기엔 너무 찔리는 감이 있음 😓
아래 그림과 같이 병사들이 있는 상황에서, 각 팀(W팀과 B팀)의 위력을 측정하는 문제로,
인접한 병사들의 수를 센 후 제곱을 하면 그게 위력이 된다.
위를 예시로 들면 아래와 같이 위력이 측정된다.
- W팀의 위력 = 9² + 7² = 130
- B팀의 위력 = 1² + 8² = 65
코드 구현 과정에 대한 설명은 아래 코드에 주석과 함께 달아두었다.
import sys
from collections import deque
# 전쟁터의 가로 크기 n, 세로 크기 m (1~100 사이 정수)
n, m = map(int, sys.stdin.readline().split()) # 5, 5
graph = list(list(sys.stdin.readline().strip()) for _ in range(m))
# 요로코롬 들어온다 [['W', 'B', 'W', 'W', 'W'], ... , ['W', 'W', 'W', 'W', 'W']]
# W : 우리 병사 / B : 적국 병사
# 상하좌우 탐색을 위한 이동 표시
dx = [-1, 1, 0, 0] # 상하좌우 이동 시 x 값이 바뀌는 정도
dy = [0, 0, -1, 1] # 상하좌우 이동 시 y 값이 바뀌는 정도
# 위력 저장할 변수
w_power = 0
b_power = 0
# N명이 뭉치면 N**2 의 위력 (대각선은 NOPE)
# 그럼 인접한 애들끼리 찾자! BFS!!
def bfs(x, y, color):
# 큐 구현
queue = deque([(x, y)]) # 최초 시작 위치는 (0, 0)
graph[x][y] = "V" # 방문한 곳은 값을 V로 바꿈
count = 1 # 뭉쳐있는 병사 수를 세기 위한 변수
while queue: # queue 가 빌 때까지 반복
x, y = queue.popleft() # 가장 먼저 삽입된 원소 꺼내기
# 꺼낸 원소의 위치에서 상하좌우 탐색
for i in range(4):
search_x, search_y = x + dx[i], y + dy[i]
# 범위 확인 필요 (그래프를 벗어나는 경우 제외) + 이미 방문한 곳인지 확인
if 0 <= search_x < m and 0 <= search_y < n:
if graph[search_x][search_y] == color:
queue.append((search_x, search_y))
graph[search_x][search_y] = "V"
count += 1
return count
for i in range(m):
for j in range(n):
if graph[i][j] == "W":
w_power += bfs(i, j, "W") ** 2
elif graph[i][j] == "B":
b_power += bfs(i, j, "B") ** 2
print(w_power, b_power)[백준][2178] 미로 탐색
BFS (너비우선탐색)
위의 전투 문제와 동일하다.
여기서는 이동할 수 있는 칸 표시인 1과 0이 문자열로 들어온다.
이미 이동한 칸은 지금까지 최소로 몇 칸 이동했는지 표시해줬고,
그 값을 튜플에 함께 담아 전달했다.
예제 입력이 아래와 같은 경우라면,
4 6
110110
110110
111111
111101BFS 탐색이 끝난 후, graph의 값은 이렇게 변경된다.
[[1, 2, '0', 8, 9, '0'],
[2, 3, '0', 7, 8, '0'],
[3, 4, 5, 6, 7, 8],
[4, 5, 6, 7, '0', 9]]모든 과정을 코드로 구현하면 아래와 같다.
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split()) # n개의 줄에 m개의 정수로 미로가 주어짐 (n x m)
# 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸
graph = list(list(sys.stdin.readline().strip()) for _ in range(n))
# 예시 : [['1', '0', '1', '1', '1', '1'], ['1', '0', '1', '0', '1', '0'], ['1', '0', '1', '0', '1', '1'], ['1', '1', '1', '0', '1', '1']]
# 상하좌우 이동값 설정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y, move=1): # move = 칸 이동 횟수
# 큐 생성
queue = deque([(x, y, move)]) # 최초로 들어온 값 (x, y, move) 큐에 삽입
graph[x][y] = move # 방문한 곳은 몇 칸 이동했는지 저장
while queue: # 큐가 비게 될 때까지 반복
x, y, move = queue.popleft()
n_move = move + 1
for i in range(4): # 상하좌우 체크
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m: # 범위 확인
if graph[nx][ny] == '1':
queue.append((nx, ny, n_move))
graph[nx][ny] = n_move
return graph[n-1][m-1]
sys.stdout.write(f"{bfs(0, 0)}")[백준][13335] 트럭
큐 (Queue)
생각의 흐름이 재밌었던 문제여서, 재밌게 풀었다.
import sys
from collections import deque
# 트럭의 순서 못 바꾸고,
# n : 다리를 건너는 트럭의 수, w : 다리의 길이, l : 다리의 최대하중
n, w, l = map(int, sys.stdin.readline().split())
# i번째 트럭의 무게 (1~10 사이 정수)
trucks = list(map(int, sys.stdin.readline().split()))
t_queue = deque(trucks)
def cross():
# 다리 위에 올라간 큐
b_queue = deque([0] * (w-1)) # 첫번째 트럭이 다 건너기 위해 가야할 시간만큼 큐에 0 으로 추가
b_queue.append(t_queue.popleft()) # 대기 중인 트럭 목록 중 첫번째 빼서 다리 위로 올리기
time = 1
while b_queue:
b_queue.popleft()
time += 1
# 대기 중인 트럭이 있을 때
if t_queue:
# 다리 위 트럭 무게 합 + 추가될 트럭 무게 합 <= 최대 하중 이어야 트럭 추가 가능
if sum(b_queue) + t_queue[0] <= l:
b_queue.append(t_queue.popleft())
# 트럭이 올라가지 못하면 공기(0가 올라간다
else:
b_queue.append(0)
return time
print(cross())[백준][15828] Router
큐 (Queue)
큐 자체를 구현하는 건 오래 안 걸렸는데,
각 테스트 케이스별로 돌려보니 에러가 뜨는 부분이 있어서, 그에 맞춰 조건을 수정해가면서 모든 테스트 케이스에 맞게 코드를 수정했다.
while True를 쓰는 걸 잠시 까먹고 있던 느낌.. 🤨
import sys
from collections import deque
# n : 라우터 내부의 버퍼 크기
n = int(sys.stdin.readline())
def router():
queue = deque()
input = int(sys.stdin.readline().strip())
queue.append(input)
# 들어오는 입력이 0 이상일 때만 반복. -1이 큐의 마지막 값으로 들어오면 반복문 종료
while True:
input = int(sys.stdin.readline().strip())
if input == -1:
break
# 0이 들어오면 한 개 처리
elif input == 0:
queue.popleft()
# 버퍼가 꽉 차 있으면 넣지 않고 다시 반복
elif len(queue) == n:
continue
else:
queue.append(input)
if len(queue) == 0:
output = "empty"
else:
output = ' '.join(str(x) for x in queue)
return output
sys.stdout.write(f"{router()}")[백준][1012] 유기농 배추 🥬
BFS (너비우선탐색)
함수 내에서 while 문을 연달아 두번 썼더니 제대로 실행이 되지 않아,
c_queue가 비었는지 확인하는 while문은 함수 밖으로 빼줬다.
import sys
from collections import deque
# t : 테스트 케이스의 개수
t = int(sys.stdin.readline())
# 상하좌우 이동
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def bfs(coordinates):
global worm
x, y = coordinates
# deque([[0, 0], [1, 0], [1, 1], [4, 2], [4, 3], [4, 5], [2, 4], [3, 4], [7, 4], [8, 4], [9, 4], [7, 5], [8, 5], [9, 5], [7, 6], [8, 6], [9, 6]])
# 지렁이 침투! -> c_queue 에서는 빼주기!
w_queue = deque([[x, y]])
c_queue.popleft()
# deque([[1, 0], [1, 1], [4, 2], [4, 3], [4, 5], [2, 4], [3, 4], [7, 4], [8, 4], [9, 4], [7, 5], [8, 5], [9, 5], [7, 6], [8, 6], [9, 6]])
while w_queue:
x, y = w_queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if [nx, ny] in c_queue:
w_queue.append([nx, ny])
c_queue.remove([nx, ny])
worm += 1
return worm
for _ in range(t):
# m : 가로 길이, n : 세로 길이, k : 배추 위치의 개수
m, n, k = map(int, sys.stdin.readline().split())
# 배추 위치
graph = list(list(map(int, sys.stdin.readline().split()))
for _ in range(k))
# [[0, 0], [1, 0], [1, 1], [4, 2], [4, 3], [4, 5], [2, 4], [3, 4], [7, 4], [8, 4], [9, 4], [7, 5], [8, 5], [9, 5], [7, 6], [8, 6], [9, 6]]
# 배추 위치도 큐로 해야지
c_queue = deque(graph)
worm = 0
while c_queue:
bfs(c_queue[0])
print(worm)