6주차
문제풀이
11725번: 트리의 부모 찾기 (acmicpc.net)
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
from collections import deque
n = int(input())
array = [[] for _ in range(n+1)]
for _ in range(n-1):
x,y = map(int,input().split())
array[x].append(y)
array[y].append(x)
q = deque()
q.append(1)
check = [0 for _ in range(n+1)]
check[1] = 1
while q:
idx = q.popleft()
for i in array[idx]:
if check[i] == 0:
q.append(i)
check[i] = idx
for i in range(2,n+1):
print(check[i])우선 각 노드에서 연결된 노드를 저장해주는 array배열을 선언해주고 이를 위에서부터 BFS로 내려오는 방식으로 풀었다. check 배열은 각 노드의 조상 노드를 저장하는 배열로, 0인지 아닌지에 따라서 방문 여부를 알 수 있다. BFS로 위에서 내려오기 때문에 A노드와 연결되어 있는 B노드로 진행할 때 B노드가 방문되지 않았다면 A노드가 B노드의 부모라는 것을 알 수 있다.
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
array = [[0 for _ in range(n)] for _ in range(n)]
array[0][0] = 2
for _ in range(k):
x,y = map(int,input().split())
array[x-1][y-1] = 1
l = int(input())
direction = 1
direction_q = deque()
snake = deque()
snake.append((0,0))
for _ in range(l):
x,y = input().split()
direction_q.append([int(x),y])
dx = [-1,0,1,0] # 북동남서
dy = [0,1,0,-1]
time = 0
x = 0
y = 0
while True:
time += 1
x += dx[direction]
y += dy[direction]
if (x,y) in snake:
break
snake.append((x,y))
if x<0 or x>=n or y<0 or y>=n:
break
if array[x][y] == 1:
array[x][y] = 0
else:
snake.popleft()
if direction_q and time == direction_q[0][0]:
if direction_q[0][1] == 'L':
direction -= 1
if direction < 0:
direction = 3
else:
direction += 1
if direction > 3:
direction = 0
direction_q.popleft()
print(time)위와 같은 어려운 구현 문제는 문제를 열심히 읽어야 한다. 단순히 읽기만 하는 것이 아니라, 읽으면서 어떤 자료형을 쓸 것이고 어떤 알고리즘을 통해서 풀 것인지 대략 감을 잡아야한다. 옳은 방법이 아니더라도 그렇게 사고 하는 과정이 실력을 키우는데에 큰 도움이 될 것이라 확신한다.
뱀 문제는 비슷한 문제가 종종 있을 정도로 유명하고 좋은 문제이다. 나는 뱀의 머리의 위치가 언젠가 꼬리의 위치가 될 것이라는 생각을 했고, 이를 queue를 통해 구현하였다. DFS나 BFS는 딱히 필요하지 않고 매 초 문제에서 원하는 방향으로 진행한다면 풀 수 있다.
14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
import sys
input = sys.stdin.readline
n = int(input())
array = []
for _ in range(n):
array.append(list(map(int,input().split())))
total = 0
for i in range(n):
for j in range(n):
total += array[i][j]
visit = [False for _ in range(n)]
visit[0] = True
count = 9999999
def DFS(v,idx):
global count
if v==n//2:
team1_count = 0
team2_count = 0
for i in range(n-1):
for j in range(i+1,n):
if visit[i] and visit[j]:
team1_count += array[i][j]
team1_count += array[j][i]
elif visit[i] == False and visit[j] == False:
team2_count += array[i][j]
team2_count += array[j][i]
count = min(count,abs(team2_count-team1_count))
return
for i in range(idx+1,n):
if visit[i] == False:
visit[i] = True
DFS(v+1,i)
visit[i] = False
DFS(1,0)
print(count)스타트와 링크 문제는 우선 n개의 팀 중 n/2 개의 팀을 DFS를 통해 구하고, 이를 통해 점수를 계산해주면 된다. True False를 통해서 True 팀과 False팀을 나누었고, 중복을 제거하기 위해 0번째 팀은 항상 True 팀으로 해주었다.
2437번: 저울
하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓
www.acmicpc.net
n = int(input())
array = list(map(int,input().split()))
array.sort()
dp = [0,array[0]]
cnt = 2
check = 0
if array[0] != 1:
check = 1
print(1)
else:
for i in range(1,n):
leng = len(dp)
check = 0
for j in range(leng):
if array[i] + dp[j] > cnt:
print(cnt)
check = 1
break
elif array[i] + j == cnt:
dp.append(cnt)
cnt += 1
if check == 1:
break
if check == 0:
print(cnt)저울 문제는 DP 문제로, 오름차순으로 정렬한 array와 작은 수부터 더해서 저장한 배열인 dp를 통해 해결하였다. 이를 cnt 변수를 통해서 해결하였는데 dp에 있는 수를 차례대로 오름차순으로 정렬한 array와 더했을 경우 무조건 오름차순으로 결과 값이 나온다는 것에 포커스를 두고 풀었다.