2025.03.30
TIL(TODAY I LEARN)
-
WEEK03 :
그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬 -
오늘도 어제에 이어서 배운 개념들을 통해 알고리즘 문제들을 풀어보자.
-
체감상 어제보다 어렵다. 이번주 문제 다 풀 수 있을까?
14888 - 연산자 끼워넣기 - 실버2
문제 링크 - https://www.acmicpc.net/problem/14888
내 코드
import sys
input = sys.stdin.readline
N = int(input().strip())
A = list(map(int,input().split()))
x = ['+', '-', '*', '/']
op1 = list(map(int,input().split()))
max_result = -float('inf')
min_result = float('inf')
op = []
for i in range(4):
op += [x[i]] * op1[i]
result = []
visited = [False] * len(op)
def per(depth, n, current):
if depth == n:
result.append(current[:])
return
prev = None #이전걸 확인해서 중복제거
for i in range(n):
if not visited[i] and op[i] != prev:
visited[i] = True
per(depth+1, n,current + [op[i]])
visited[i] = False
prev = op[i]
op.sort() #이전게 같은 수라면 중복 제거를 위해 정렬해야함
per(0,len(op),[])
for i in range(len(result)):
value = A[0]
for a in range(len(op)):
if result[i][a] == '+':
value += A[a+1]
elif result[i][a] == '-':
value -= A[a+1]
elif result[i][a] == '*':
value *= A[a+1]
elif result[i][a] == '/':
if value < 0:
value = -1*((value * -1) // A[a+1])
else:
value = value // A[a+1]
if max_result < value:
max_result = value
if min_result > value:
min_result = value
print(max_result)
print(min_result)- 백트래킹이 기법이 필요했다.
문제 분류
2573 - 빙산 - 골드4
문제 링크 - https://www.acmicpc.net/problem/2573
내 코드
import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
graph = []
for i in range(N):
graph.append(list(map(int,input().split())))
# 상 하 좌 우
dx = [0,0,-1,1]
dy = [-1,1,0,0]
def next_year():
temp = [[0]*M for _ in range(N)]
for i in range(N):
for j in range(M):
coor = graph[i][j]
if coor != 0:
cnt_zero = 0
for a,b in zip(dx,dy):
nx = a + i
ny = b + j
if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
cnt_zero += 1
if coor - cnt_zero <= 0:
temp[i][j] = 0
else:
temp[i][j] = graph[i][j] - cnt_zero
return temp
def bfs(x,y):
visited[x][y] = 50 #방문처리 50으로 해주자
q = deque([(x,y)])
while q:
u,v = q.popleft()
for i in range(4):
nx = u + dx[i]
ny = v + dy[i]
if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] != 50 and graph[nx][ny] != 0:
q.append((nx,ny))
visited[nx][ny] = 50
year = 0
while True:
visited = [[0] * M for _ in range(N)]
seom_cnt = 0
for i in range(N):
for j in range(M):
if graph[i][j] != 0 and visited[i][j] != 50:
bfs(i,j)
seom_cnt += 1
if sum(map(sum,graph)) == 0:
print(0)
break
if seom_cnt != 1:
print(year)
break
graph = next_year()
year += 1
문제 분류
2617 - 구슬 찾기 - 골드4
문제 링크 - https://www.acmicpc.net/problem/2617
내 코드
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
graph_hi = [[] for _ in range(N+1)]
graph_lo = [[] for _ in range(N+1)]
for _ in range(M):
u,v = map(int,input().split())
graph_hi[u].append(v)
graph_lo[v].append(u)
mid = (N+1)//2
def dfs(visited,start,graph):
visited[start] = True
for x in graph[start]:
if visited[x] == False:
dfs(visited,x,graph)
result = 0
for i in range(1,N+1):
visited_h = [False] * (N+1)
visited_l = [False] * (N+1)
dfs(visited_h,i,graph_hi)
dfs(visited_l,i,graph_lo)
#visited_h,_l 배열에 자기자신도 True 이기 때문에 -1 해서 더 크거나 더 작은 구슬만 찾아야 함
if visited_h.count(True)-1 >= mid or visited_l.count(True)-1 >= mid:
result += 1
print(result)
다른 코드(플로이드-와샬 알고리즘 이용)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dist = [[False] * (N + 1) for _ in range(N + 1)]
# A > B (A가 B보다 무겁다)
for _ in range(M):
a, b = map(int, input().split())
dist[a][b] = True
# 플로이드-워셜: 간접 무게 관계 파악
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
if dist[i][k] and dist[k][j]:
dist[i][j] = True
mid = (N + 1) // 2
answer = 0
for i in range(1, N + 1):
heavier = sum(dist[i][1:]) # i보다 가벼운 애들 수
lighter = sum(dist[j][i] for j in range(1, N + 1)) # i보다 무거운 애들 수
if heavier >= mid or lighter >= mid:
answer += 1
print(answer)
문제 분류
점점 구현이 복잡해지는 느낌이다. 어렵다 어려워
^_^