[99클럽 코테 스터디 TIL 13일차 / 백준 2529] 부등호 (Python)

 

처음에 문제를 읽고 일단 그래프 탐색이니까 BFS를 사용해야겠다고 생각했다. 큰 이유는 없었고 매번 BFS만 사용해서 DFS는 생소했기 때문이다.

 

그러던중, 이 문제는 브루트포스 알고리즘 관련 문제라는 것을 알게 되었다. 

 

브루트포스는 먼저 한 방향으로 탐색을 하고 더이상 답이 없을 경우엔 되돌아와 다른 방향을 탐색하는 것이다.

그렇기 때문에 브루트포스는 BFS가 아닌 DFS가 적합하다고 판단하였다.

 

내 코드

from collections import deque

k = int(input())

sign = list(input().split())

min_n = ''
max_n = ''
visited = [0 for _ in range(11)]
def dfs(cnt, s):
    global min_n, max_n
    if cnt == k:
        if len(min_n) == 0: min_n = s
        else: max_n = s
        return
    for i in range(0, 10):
        if len(s) == 0:
            visited[i] = 1
            dfs(cnt + 1, str(i))
            visited[i] = 0
        elif visited[i] == 0:
            if sign[cnt] == '>' and i < int(s[-1:]) :
                visited[i] = 1
                dfs(cnt + 1, s + str(i))
                visited[i] = 0
            elif sign[cnt] == '<' and i > int(s[-1:]) : 
                visited[i] = 1
                dfs(cnt + 1, s + str(i))
                visited[i] = 0

dfs(-1, '')

print(max_n)
print(min_n)

코드가 좀.. 매우 더럽다. 긴 연휴뒤에 다시 공부를 시작하려니 오늘 집중이 너무너무 안됐다.

이 문제만 3시간 잡고 있었던 듯,, 결국 다른 사람 코드도 참고하였다.

 

dfs 함수의 인자는 순서에 따른 부등호 인덱스 번호와 누적으로 숫자가 합해질 문자열이다.

처음 인자로는 부등호 인덱스 -1과 빈 문자열을 넘겨주었다.

 

DFS 함수

if cnt == k:
	if len(min_n) == 0: min_n = s
    else: max_n = s
    return

1. cnt == k 인 경우는 모든 부등호를 충족한 숫자를 찾았다는 의미이기 때문에 그 숫자를 min_n 또는 max_n에 넣어줘야 한다. 그런데 탐색하는 숫자는 점점 커지기 때문에 자연스럽게 처음으로 충족하는 숫자는 min_n이고 마지막으로 찾은 충족하는 숫자는 max_n이기 때문에 max_n 값은 충족하는 숫자를 찾을때마다 업데이트해주었다. 그리고 모든 부등호를 충족하였으니 return을 통해 해당 재귀함수를 끝내준다.

 

for i in range(0, 10):
    if len(s) == 0:
    	visited[i] = 1
        dfs(cnt + 1, str(i))
        visited[i] = 0

2. 0 부터 9까지 뒤에 오는 숫자를 모두 탐색하는데 s문자열이 빈 문자열인건 첫번째 자리 숫자를 지정하는 것이기 때문에 부등호 비교를 할 수 없기 때문에 바로 cnt + 1, str(i)를 인자로 넘겨 재귀함수를 호출한다. 여기서 재귀함수 호출 전에는 visited에 1을 넣어주고 호출 후에는 visited에 0을 넣어주는 이유는 해당 방향으로 그래프탐색을 할때에는 이 앞에 어떤 숫자를 방문했는지 필요하지만 재귀함수가 끝난 이후에는 다른 방향으로 그래프 탐색을 하기에 visited 리스트를 초기화해줘야 하기 때문이다.

 

elif visited[i] == 0:
    if sign[cnt] == '>' and i < int(s[-1:]) :
        visited[i] = 1
        dfs(cnt + 1, s + str(i))
        visited[i] = 0
    elif sign[cnt] == '<' and i > int(s[-1:]) : 
        visited[i] = 1
        dfs(cnt + 1, s + str(i))
        visited[i] = 0

3. 첫번째 자리 숫자가 아니라면, 이미 방문한 숫자가 아니고 해당 위치의 부등호에 적합한 숫자라면 방문했다고 표시하고 cnt + 1과 문자열에 해당 숫자를 추가한 인자를 넘기는 재귀함수를 호출한다. 여기도 재귀함수 호출 뒤에는 visited 리스트를 다시 초기화 해준다.

 

 

끝 !

 

흐앙 오늘 TIL 안쓸까하다가 그럼 너무 루즈해진거 같아서 억지로 썼다 !

그래도 확실히 TIL 쓰니까 내가 어떤 생각을 했고 어떤 방법으로 문제를 풀었는지 정리가 돼서 좋다.

이제 연휴 끝났으니 다시 공부 집중 !

 

오늘 오전에 코테를 봤는데 나쁘지 않게 본 것 같다 ! ㅎㅎ

코테 문제 형식이 한문제 당 1-1, 1-2, 1-3, 1-4, 1-5 이렇게 5단계의 문제가 있었다. 그런데 이걸 모르고 1번에 1단계만 풀고 2번 1~5단계를 풀고난 뒤에야 1번도 5단계까지 문제가 있다는 걸 깨달았다 ..

그래서 거의 다 풀긴 했지만 1번 5단계 80점까지 풀고 제출했다..

어쩐지 2번 푸는데 시간도 너무 많이 남고 쉽더라 ㅜㅜ 10분만 더 있었어도 1번도 다 풀었을텐데.. 조금은 아쉽다 ..!!

하지만 거의 다 풀은거로 만족 ㅎ히히

제발 합격했으면 좋겠다 !!