✅ 문제 풀이
🎈 2636 치즈
입력값으로 세로와 가로를 입력받아 직사각형을 만들고 치즈가 있는 칸, 없는 칸을 입력받는다
그 후 치즈가 있는 칸은 1시간마다 공기와 닿은 면이 있으면 녹게 된다. 이때 치즈가 다 녹는데 걸린 시간과 다 녹기 직전에 존재한 치즈 개수를 출력하는 문제.
+) 가장자리에는 치즈가 놓일 수 없고 치즈에는 하나 이상의 공기 구멍이 존재할 수 있고 치즈 구멍 내 공기와 치즈의 접촉은 무시한다.
import sys
input = sys.stdin.readline
from collections import deque
# 세로 가로 입력
n, m = map(int, input().split())
graph = []
# 그래프 입력
for _ in range(n):
graph.append(list(map(int, input().split())))
# 상하좌우 4방향 기준
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 매 시간마다 치ㄱ즈가 녹고 남은 치즈 수
answer = []
# bfs 함수
def bfs():
queue = deque()
# 큐에 초기값 삽입
queue.append([0, 0])
# 초기값 방문 처리
visited[0][0] = 1
# 녹은 치즈수 체크
cheese = 0
# 큐가 빌 때까지
while queue:
x, y = queue.popleft()
# 4방향 탐색
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 주어진 범위 내 방문하지 않은 곳에 한해
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
# 다음 좌표가 치즈가 없는 곳이면
if graph[nx][ny] == 0:
# 방문처리 하고 큐에 다음 위치 넣기 (가장자리 체크)
visited[nx][ny] = 1
queue.append((nx, ny))
# 다음 위치에 치즈가 있으면
elif graph[nx][ny] == 1:
# 다음 위치가 방문한적없고, 치즈가 있는 곳이면 가장자리이므로
# 방문처리 후 치즈 녹은 것 표시하고 치즈 수 카운팅
visited[nx][ny] = 1
graph[nx][ny] = 0
cheese += 1
answer.append(cheese)
return cheese
time = 0
# 치즈가 녹을때까지 진행
while True:
# 1시간 지난 것 체크
time += 1
# 매 시간 방문여부 확인
visited = [[0]*m for _ in range(n)]
# bfs 탐색으로 치즈 수 체크
cheese = bfs()
# 치즈가 다 녹았으면 중단
if cheese == 0:
break
print(time - 1)
print(answer[-2])< 풀이 과정 >
bfs 탐색을 활용한 풀이
매 시간마다 visited로 방문여부 확인하고 bfs탐색을 통해 cheese수를 체크해 치즈가 다 녹았을 때 중단하고 결과를 출력하도록 하였다.
bfs탐색을 자세히 살펴보면, 주어진 범위 내 그래프 안에 방문하지 않은 곳에 한해서
- 다음 위치에 치즈가 없는 경우 방문처리하고, 큐에 다음 위치를 넣어준다.
- 다음 위치에 치즈가 있는 경우 방문처리하고 치즈가 녹았음을 표시해주고 치즈 수를 + 1해준다.
🎈 13549 숨바꼭질 3
n에서 k로 이동하는 과정에서 현 위치가 x라면 x-1, x+1, 2x 칸으로 이동이 가능하다. 이때 2x로 이동하게 되면 걸리는 시간은 0초이고 나머지는 +1초 씩일때 n에서 k로 이동하는 최소 시간을 구하는 문제
from collections import deque
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
def bfs():
# 방문 여부 확인
visited = [0] * 100001
visited[n] = 1
queue = deque()
queue.append(n)
while queue:
x = queue.popleft()
# 다음 칸이 도착점이면
if x == k:
# 1부터 시작하므로 -1 처리해주기
print(visited[k] - 1)
break
# 이동 가능 영역 중
for next in (x-1, x+1, 2*x):
# 범위를 만족하면서 다음칸을 방문한 적 없으면
if 0 <= next < 100001 and visited[next] == 0:
# 3가지 경우 중 다음 칸이 2*x라면
if 2*x == next:
visited[next] = visited[x]
queue.appendleft(next)
# 나머지의 경우
else:
visited[next] = visited[x] + 1
queue.append(next)
bfs()< 풀이 과정 >
BFS를 이용하여 쉽게 구현하였다.
시간을 재기 위해 visited 1차원 리스트를 만들어 현 위치를 1로 처리하고 다음 위치가 k라면 현위치 -1을 출력하고 중단한다. 아닌 경우 x-1, x+1, x2의 3 경우 중 범위 내에 있고 아직 들리지 않은 곳에 한해 탐색을 진행하는데, 2x이면 값 그대로, 아닌 경우 +1초를 처리해 bfs()함수를 실행시켜 리턴한다.
🎈 11403 경로 찾기
가중치 없는 유향 그래프 G가 주어진다.
그래프는 모든 정점 (i,j)에 대해 i번째 줄의 j번째 숫자가 1인 경우 (i,j)인 간선이 있고 0이면 간선이 없다는 뜻일 때, 그래프 간 이동이 가능한 간선들을 입력 형태와 유사하게 출력하는 문제
from collections import deque
# 입력, 그래프, 방문 여부
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]
def bfs(x):
queue = deque()
queue.append(x)
# col단위로 검열 (인덱스 느낌)
check = [0 for _ in range(n)]
while queue:
p = queue.popleft()
# 모든 col에 대해 탐색 진행
for i in range(n):
# 현 위치 col에서 값 0이고, graph에선 1로 간선이 있다면
if check[i] == 0 and graph[p][i] == 1:
# 큐에 넣고, 값 변경해주고 visited 처리
queue.append(i)
check[i] = 1
visited[x][1] = 1
# 모든 row에 대해 진행하여 visited 출력하기
for i in range(0, n):
bfs(i)
for i in visited:
print(*i)# DFS
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [0 for _ in range(n)]
def dfs(x):
# 모든 col에 대해
for i in range(n):
# row 고정으로 col에 위치값이 1이고 방문한적 없으면 방문 처리후 dfs재귀
if graph[x][i] == 1 and not visited[i]:
visited[i] = 1
dfs(i)
# 모든 row에 대해 진행
for i in range(n):
dfs(i)
for j in range(n):
# 방문한 적 있다. 즉 간선이 존재한다면
if visited[j] == 1:
print(1, end = ' ')
else:
print(0, end = ' ')
print()
# 한번 돌고나서 visited는 초기화 해주는 것 필요
visited = [0 for _ in range(n)]# Floyd-Warshall
import sys
input = sys.stdin.readline
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
# 3중 for문으로 j > i 경로가 있고, i > k 경로가 있다면 j > k 역시 경로가 있다.
for i in range(n):
for j in range(n):
for k in range(n):
if graph[j][i] and graph[i][k]:
graph[j][k] = 1
for i in graph:
print(*i)< 풀이 과정 >
최근 그래프 알고리즘을 학습하며 배운 플로이드-워셜을 활용하였고 이외에도 BFS, DFS를 활용하여 풀이를 진행했다. 주석참고 하기
