백준 알고리즘 풀이 모음 14590, 2469, 1107 (Feat Python)
백준 14590번 KUBC League (Small)
N명의 정회원들이 리그에 참여하여 N(N-1)/2번의 경기를 진행하고, 1번 선수가 자신이 이긴 사람과 해당 사람이 이긴 사람들의 꼬리를 무는 선수 나열을 통해 얻을 수 있는 최대 길이 L을 출력하는 문제입니다.
문제 조건
- 2 <= N <= 50
- 각 선수의 이기고 진 경우를 N*N 크기의 행렬로 주어진다 i,j는 i 선수가 j 선수와의 경기에서 이겼는지 졌는지를 나타낸다. 이겼을 경우 1 졌을 경우 0
- 2번 선수가 3번 선수에게 이겼을 경우 arr[2][3]=1 arr[3][2]=0 입니다.
아이디어
1. 탐색 방법
(1번 선수)가 이긴 선수 -> (1번 선수에게 진 선수)가 이긴 선수 -> (1번 선수에게 진 선수에게 진 선수)가 이긴 선수 -> ... 방향으로 탐색하여 최대 길이를 구합니다.
DFS를 통해 최대 길이를 구합니다.
2. 최적화 방법
각 선수마다 위처럼 자신에게 진 선수를 나열했을 때의 최대 길이를 가지고 있을 것이고 이는 변하지 않습니다. -> 캐싱을 통해 어떤 선수가 이미 자신에게 진 선수들을 나열해 최대 길이를 가지고 있을 경우 이를 바로 활용하여 더 탐색하지 않고도 최대 길이를 반환할 수 있도록 합니다.
풀이
변수 선언
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
maxPath = [[] for _ in range(N)]
visited = [False for _ in range(N)]
maxPath는 각 선수마다 자신의 최대 길이를 저장할 수 있도록 합니다.
visited를 통해 이미 방문한 곳인지 확인해줍니다.
DFS
def findMaxPath(node):
if len(maxPath[node]) != 0:
return maxPath[node][:]
returnMaxPath = [node]
tempMaxPath = []
for nextNode in range(N):
if board[node][nextNode] == 0 or visited[nextNode]:
continue
visited[nextNode] = True
temp = findMaxPath(nextNode)
visited[nextNode] = False
if len(temp) > len(tempMaxPath):
tempMaxPath.clear()
tempMaxPath.extend(temp[:])
returnMaxPath.extend(tempMaxPath[:])
maxPath[node].extend(returnMaxPath[:])
return maxPath[node][:]
findMaxPath를 통해 dfs를 해줍니다.
탐색하는 선수마다 자신의 최대 길이를 구했다면 이를 저장하여 다음 검색 때 활용할 수 있도록 해줍니다.
2468번 안전 영역
N*N 칸에 각 지역의 높이가 주어지고 비가 올 때 안전한 영역의 최대 개수를 구하는 문제입니다.
문제 조건
- 2 <= N <= 100
- 1 <= 각 칸의 높이 <= 100
아이디어
1. 영역 찾기
물이 오는 높이에 따라 안전한 영역을 찾을 경우 물의 높이보다 높은 영역이 있을 경우 해당 지역부터 dfs나 bfs를 활용하여 안전한 영역을 찾아줍니다.
2. 완전 탐색?
모든 칸을 탐색할 경우 최대 10,000 그리고 비가 올 수 있는 모든 높이를 탐색하면 최대 1,000,000번 탐색을 하게 됩니다. 문제 조건이 그렇게 큰 경우는 아니므로 모두 탐색해서 안전한 영역의 최대 개수를 찾을 수 있습니다.
풀이
변수
N = int(input())
board = []
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
maxHeight = 0
minHeight = 101
minHeight와 maxHeight에 최소 높이와 최대 높이를 찾고 비가 올 때 영향을 받게 될 범위에서만 탐색하도록 했습니다.
DFS
answer = 1
for h in range(minHeight, maxHeight+1):
visited = [[False for _ in range(N)] for __ in range(N)]
temp = 0
for i in range(N):
for j in range(N):
if visited[i][j] or board[i][j] <= h:
continue
temp += 1
stack = [(i, j)]
while stack:
ci, cj = stack.pop()
for k in range(4):
ni, nj = ci+moves[k][0], cj+moves[k][1]
if not (0 <= ni < N and 0 <= nj < N) or visited[ni][nj] or board[ni][nj] <= h:
continue
visited[ni][nj] = True
stack.append((ni, nj))
answer = max(answer, temp)
각 높이 경우마다 visited를 통해 방문한 칸은 다시 방문하지 않도록 했습니다.
백준과 같은 경우 재귀를 통해 문제 풀이를 할 경우 최대 재귀 함수 호출 횟수를 제한두어서 이를 따로 설정해주어야 하는 경우가 종종 발생해 이번에는 stack을 선언해서 풀이해주었습니다.
비의 높이보다 높은 칸이 나오면 해당 칸을 포함하는 영역을 모두 찾아 하나의 영역으로 표시해주었고, 이러한 영역의 개수를 temp에 저장했습니다.
비가 올 높이마다 answer와 temp를 비교하여 최대값을 찾을 수 있도록 했습니다.
백준 1107번 리모컨
리모컨의 0~9번 버튼과 +,-버튼이 있고 숫자 번호의 경우 고장날 경우가 있을 경우, 주어진 번호로 갈 수 있는 최소 버튼 클릭 횟수를 구하는 문제입니다. 현재 번호는 100번
문제 조건
- 0 <= N <= 500,000
- 0 <= 고장난 버튼 개수 <= 10
아이디어
1. 이동하려는 번호가 100일 경우
이동하지 않아도 이미 100번이므로 0을 출력하고 종료합니다.
2. 숫자 번호를 누르는 경우
만약 100에서 +, - 버튼을 눌러서 이동이 빠른 경우 +, - 버튼만으로도 이동이 가능합니다.
하지만, 그 외의 모든 경우는 먼저 숫자 버튼을 눌러주어야 합니다. 그러므로 초기 숫자버튼을 통해 해당 숫자 주위로 이동한 뒤 +, - 버튼을 통해 해당 숫자로 이동합니다.
숫자 번호를 누른 뒤 +, -를 누르는 횟수는 숫자 번호를 이동한 번호에서 이동하려는 번호를 뺀 것과 같습니다. 그러므로 문제는 +, - 버튼을 누르는 횟수를 줄여주어야 합니다.
3. dfs
찾아야 하는 번호가 최대 6자리이고 각 자리마다 탐색해야하는 최대의 개수가 500,000이므로 모든 경우의 탐색해도 시간 초과가 발생하지 않을 것이라고 생각했습니다.
4. 주의 해야 하는 경우
고장난 번호가 있기 때문에 해당 숫자에 가장 가까운 번호로 이동할 경우 +, - 버튼을 눌러 이동하는 경우까지 합해서 계산해줍니다.
현재 번호가 100이므로 100에서 +, - 버튼만을 눌러 이동하는 경우가 더 적은 횟수일 경우도 존재합니다.
풀이
변수 선언
N = int(input())
M = int(input())
length = len(str(N))
brokenList = [False for _ in range(10)]
if N == 100:
print(0)
exit()
...
answer = abs(100-N)
dfs(0, 0)
print(answer)
brokenList에 고장난 번호를 저장했습니다.
answer는 100번에서 +, -로만 이동할 경우 누르는 버튼의 횟수로 초기화 해주었습니다. 이 후 dfs를 통해 최소 회수를 구할 수 있도록 했습니다.
dfs
def dfs(i, cur):
global answer
if i != 0 and length - 1 <= i <= length+1:
answer = min(answer, abs(N-cur)+len(str(cur)))
if i == length+1:
return
for k in range(10):
if brokenList[k]:
continue
dfs(i+1, cur*10+k)
dfs를 통해 고장나지 않은 번호를 눌러나감으로써 해당 번호의 주위까지 숫자 번호를 누를 수 있도록 해줍니다.
+, - 버튼을 누르는 횟수를 줄이는 방법은 우선 이동하려는 번호의 숫자 길이와 비슷하게 숫자 버튼을 눌러 만들어주는 것입니다.
이 비슷하다는 범위를 저와 같은 경우 이동하려는 번호의 길이 ± 1로 선정했습니다. 그리고 이 범위 안에 만들 수 있는 숫자에서 +, - 버튼을 누르는 횟수를 더해서 최소 회수를 구할 때, 한 번에 찾기에는 어려우므로 모든 경우의 수를 탐색하도록 했습니다.
단, 이동하려는 번호의 길이가 1일 경우 위의 조건으로 풀이 시 문제가 생길 수 있으므로 주의하여 조건을 세워주어야 합니다.
만들어진 숫자의 길이가 이동하려는 숫자의 길이보다 1 큰 경우, 이보다 더 숫자 버튼을 누를 경우 버튼을 누르는 횟수가 현저히 늘기 때문에 재귀를 return 하도록 했습니다.