⚔️ 백준

---

📌 1948 임계경로

import sys
sys.setrecursionlimit(10**5)

def dfs(road,total_time):
    # 도로를 달리고 난 뒤 정보 갱신
    a,t = road
    total_time += t # 도로의 시간 더하기
    if a == arrive:
        return total_time
    # 다음 도로 달릴 계획
    for next_road in city[a]:
        return dfs((next_road),total_time)

n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
city={i:[] for i in range(n+1)}
for _ in range(m):
    s,a,t = map(int,input().split())
    city[s].append((a,t)) # s: 출발, a: 도착, t: 걸리는시간
start, arrive = map(int,input().split())
# dfs로 하나 조진 후에 시간 입력, 최대 시간 찾기

# 시작 도시에서 출발 시작
stack=[]
for a, t in city[start]:
    stack.append(dfs((a,t),0))
print(max(stack))

단순히 스택으로 하기에 복잡할 것 같아서 재귀로 접근.

예제 시각화했던거랑 비교해보니까 9가 빠짐.
생각해보니까 단순히 return 때려버리면 안됨.
그럼 경로당 하나의 경로만 return됨.

import sys
sys.setrecursionlimit(10**5)

def dfs(road,road_cnt,total_time):
    # 도로를 달리고 난 뒤 정보 갱신
    a,t = road
    total_time += t # 도로의 시간 더하기
    if a == arrive:
        stack.append((road_cnt+1,total_time))
        return 
    # 다음 도로 달릴 계획
    for next_road in city[a]:
        dfs((next_road),road_cnt+1,total_time)

n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
city={i:[] for i in range(n+1)}
for _ in range(m):
    s,a,t = map(int,input().split())
    city[s].append((a,t)) # s: 출발, a: 도착, t: 걸리는시간
start, arrive = map(int,input().split())
# dfs로 하나 조진 후에 시간 입력, 최대 시간 찾기
# 제일 마지막에 도착하는 사람들이 달린 도로의 개수를 알아야 함

# 시작 도시에서 출발 시작
stack=[]
for a, t in city[start]:
    dfs((a,t),0,0)
print(stack)

리스트는 global 안 써도 함수 안에서 사용 가능하다는 점을 이용하여 (global 안 쓰면 그냥 stack=[1,2,3] 이런식으론 못 쓰는듯) 종료 조건에서 전역 변수 stack에 해당 경로의 road_cnt와 total_time에 대한 정보를 추가하고 종료

7
9
1 2 4
1 3 2
1 4 3
2 6 3
2 7 5
3 5 1
4 6 4
5 6 2
6 7 5
1 7
[(3, 12), (2, 9), (4, 10), (3, 12)]

그랬더니 뭔가 이상함.
예제 답과 다름.
1분도 쉬지 않고 달려야 하는 도로의 수가 겹치면 중복은 삭제해야됨. 좀 악랄한듯;

경로에 대한 정보를 저장하고
아무것도 없으면 자기로 초기화,
들어있는 시간이 자기보다 작으면 자기로 초기화,
들어있는 시간이 자기랑 같으면 자기도 추가,
들어있는 시간이 자기보다 크면 못 들어감

import sys
sys.setrecursionlimit(10**5)

def dfs(road,road_cnt,total_time,history):
    # 도로를 달리고 난 뒤 정보 갱신
    a,t = road
    total_time += t # 도로의 시간 더하기
    if a == arrive:
        stack.append((road_cnt+1,total_time,history))
        return 
    # 다음 도로 달릴 계획
    for next_road in city[a]:
        history.append((a,next_road[0]))
        dfs(next_road,road_cnt+1,total_time,history)
        history.pop()

n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
city={i:[] for i in range(n+1)}
for _ in range(m):
    s,a,t = map(int,input().split())
    city[s].append((a,t)) # s: 출발, a: 도착, t: 걸리는시간
start, arrive = map(int,input().split())
# dfs로 하나 조진 후에 시간 입력, 최대 시간 찾기
# 제일 마지막에 도착하는 사람들이 달린 도로의 개수를 알아야 함

# 시작 도시에서 출발 시작
stack=[]
for a, t in city[start]:
    dfs((a,t),0,0,[(start,a)])
print(stack)

근데 경로 저장하려는데 백트래킹이 안되고 리스트가 이후 상황에 의해 초기화되는 상황 발생

        # history.append((a,next_road[0]))
        dfs(next_road,road_cnt+1,total_time,history+[(a,next_road[0])])
        # history.pop()

append 대신 더하기로 해결
저번에 비슷한 상황 있었는데 까먹고 또 이렇게 했네

경로 중복 해결하는 원래 계획은 set 쓰는 거였는데
연산이 좀 비쌀 것 같아서

각 경로를 인덱스로 추상화하면 되지 않을까 싶었는데
또 그러면 아예 코드를 갈아 엎어야되니까
일단 set로 해보기로 함

import sys
sys.setrecursionlimit(10**5)

def dfs(road,total_time,history):
    # 도로를 달리고 난 뒤 정보 갱신
    global stack
    a,t = road
    total_time += t # 도로의 시간 더하기
    # 아무것도 없으면 자기로 초기화,
    # 들어있는 시간이 자기보다 작으면 자기로 초기화,
    # 들어있는 시간이 자기랑 같으면 자기도 추가,
    # 들어있는 시간이 자기보다 크면 못 들어감
    if a == arrive:
        if not stack or stack[0][0] < total_time:
            stack = [(total_time,history)]
        elif stack[0][0] == total_time:
            stack.append((total_time,history))
        return 
    # 다음 도로 달릴 계획
    for next_road in city[a]:
        dfs(next_road,total_time,history+[(a,next_road[0])])


n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
city={i:[] for i in range(n+1)}
for _ in range(m):
    s,a,t = map(int,input().split())
    city[s].append((a,t)) # s: 출발, a: 도착, t: 걸리는시간
start, arrive = map(int,input().split())
# dfs로 하나 조진 후에 시간 입력, 최대 시간 찾기
# 제일 마지막에 도착하는 사람들이 달린 도로의 개수를 알아야 함

# 시작 도시에서 출발 시작
stack=[]
for a, t in city[start]:
    dfs((a,t),0,[(start,a)])
# print(stack)
final_course=set()
for course in stack:
    for road in course[1]:
        final_course.add(road)
print(stack[0][0])
print(len(final_course))

예제 case는 맞았는데 시간초과.
set에 add하는 부분 주석처리했는데도 시간 초과.
경로 history 부분을 아예 삭제했는데도 시간 초과.

로직이 뭔가 잘못된듯?
반복문으로 했어야 했나?

'최대' 시간이 소요되는 경로니까 dp 가미해서
도착한 도시에 적힌 시간이 자기보다 높으면 경로 취소하면 계산량 줄어들듯

    # 도착한 도시에 적힌 시간이 자기보다 높으면 경로 취소
    if city_time[a] > total_time:
        return
    city_time[a] = total_time

이거 추가했더니 7%까지는 올라가는데
역시 시간 초과 뜸.

def dfs_all_paths_iterative(graph, start, end=None):
    stack = [(start, [start])]  # 스택에 (현재 노드, 경로)를 저장
    all_paths = []               # 모든 경로를 저장할 리스트

    while stack:
        (vertex, path) = stack.pop()  # 스택에서 현재 노드와 경로를 꺼냄

        # 탐색을 원하는 끝 노드를 지정한 경우
        if end and vertex == end:
            all_paths.append(path)
            continue

        for neighbor in reversed(graph.get(vertex, [])):
            if neighbor not in path:  # 사이클을 방지하기 위해 이미 경로에 있는 노드는 제외
                stack.append((neighbor, path + [neighbor]))

    return all_paths

# 그래프 정의 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 특정 끝 노드까지의 모든 경로 출력 (예: 'F')
all_paths_to_F = dfs_all_paths_iterative(graph, 'A', end='F')
print("\n'A'에서 'F'까지의 모든 경로들:")
for path in all_paths_to_F:
    print(" -> ".join(path))

gpt한테 dfs 반복문으로 할 때 모든 경로 출력 어떻게 하냐고 물어봄

대충 알긴 하겠는데 아직 눈에 안 익음

def dfs(start,arrive):
    courses = [(start, 0, [])]
    result = []

    while courses:
        course = courses.pop()
        start, total_time, history = course

        # 최대 시간을 가진 경로가 아니라면 더 탐색하지 않음
        if city_time[start] > total_time:
            continue
        else:
            city_time[start] = total_time

        # 도착지에 도착했다면 result에 저장
        if start == arrive:
            if not result or result[0][1] < total_time:
                result = [course]
            elif result[0][1] == total_time:
                result.append(course)

        # 도시에서 이어지는 경로들을 추가해줌
        for road in city[start]:
            next, time = road
            courses.append((next,total_time+time,history+[(start,next)]))
    
    return result


n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
city={i:[] for i in range(n+1)}
city_time = [0 for _ in range(n+1)] # 경로 가지수 제거용
for _ in range(m):
    s,a,t = map(int,input().split())
    city[s].append((a,t)) # s: 출발, a: 도착, t: 걸리는시간
start, arrive = map(int,input().split())
# dfs로 하나 조진 후에 시간 입력, 최대 시간 찾기
# 제일 마지막에 도착하는 사람들이 달린 도로의 개수를 알아야 함

all_course = []
# 시작 도시에서 출발 시작
all_course = dfs(start,arrive)
print(all_course[0][1])
final_course=set()
for course in all_course:
    for road in course[2]:
        final_course.add(road)
print(len(final_course))

참고해서 코드 짜긴 했는데
이번엔 11%에서 시간 초과 당함

반복문으로 했는데도 안되는 거면 로직에서 뭔가 크게 잘못 생각하고 있는게 확실

bfs로 바꾼다고 해도 획기적으로 경우의 수가 줄어들 것 같진 않음

그래서 문제 유형을 봤더니 dfs bfs가 아니라 위상 정렬이었답니다~ ㅋㅋㅋ

dfs bfs 따위를 아무리 깎아봤자 특수한 알고리즘은 못 이긴다는 걸 깨달았다

도로 개수 10만개라 2억까지 2000회 순회 돌릴 수 있는 여유 있어서 될 거라고 생각했는데 안되는구나

그리고 유형을 모르고 푸니까 전혀 위상 정렬일거라고 생각이 안 들었다. 뭔가 특수한 조건을 충족했으니까 특수한 알고리즘을 쓸 수 있었던 거겠지?

내일 위상 정렬 다시 공부하고 풀어봐야할듯.
(+ 저번에 못 풀었던 ACM craft도 위상 정렬 문제였나?)

📌 2667 단지번호붙이기

Map=[list(map(int,input().split())) for _ in range(N)]

스페이스바로 나눠져있지도 않은데 무지성으로 map 써버린 실수

다 풀고 다시 확인해봤더니 이거 되는데?? 뭐지

아 split()을 안하면 되는 거였구나

N=int(input())
Map = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    str = input()
    for j in range(N):
        Map[i][j] = int(str[j])
dx, dy = [1,-1,0,0], [0,0,1,-1]
apts=[]
for i in range(N):
    for j in range(N):
        if Map[i][j] == 1:
            apt = 0
            stack=[(i,j)]
            while stack:
                x,y=stack.pop()
                if Map[x][y]==1:
                    Map[x][y]=0
                    apt+=1
                    for k in range(4):
                        if 0<=x+dx[k]<N and 0<=y+dy[k]<N:
                            if Map[x+dx[k]][y+dy[k]] == 1:
                                stack.append((x+dx[k],y+dy[k]))
            apts.append(apt)
print(len(apts))
apts.sort()
for apt in apts:
    print(apt)

코드 길이 조금 길어져도 dfs로 따로 빼내는게 더 보기 좋은듯

def dfs(i,j):
    apt = 0
    stack=[(i,j)]
    while stack:
        x,y=stack.pop()
        if Map[x][y]==1:
            Map[x][y]=0
            apt+=1
            for k in range(4):
                if 0<=x+dx[k]<N and 0<=y+dy[k]<N:
                    if Map[x+dx[k]][y+dy[k]] == 1:
                        stack.append((x+dx[k],y+dy[k]))
    apts.append(apt)


N=int(input())
Map = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    str = input()
    for j in range(N):
        Map[i][j] = int(str[j])
dx, dy = [1,-1,0,0], [0,0,1,-1]
apts=[]
for i in range(N):
    for j in range(N):
        if Map[i][j] == 1:
            dfs(i,j)

print(len(apts))
apts.sort()
for apt in apts:
    print(apt)

단순히 뚝 잘라서 복붙만 했는데도 살짝 보기 좋...나?
잘 모르겠는거같기도

N=int(input())
Map = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    str = input()
    for j in range(N):
        Map[i][j] = int(str[j])
dx, dy = [1,-1,0,0], [0,0,1,-1]
apts=[]
for i in range(N):
    for j in range(N):
        if Map[i][j] == 1:
            apt = 0
            stack=[(i,j)]
            # dfs 돌려서 아파트 칠해버리기
            while stack:
                x,y=stack.pop()
                if Map[x][y]==1:
                    Map[x][y]=0
                    apt+=1
                    for k in range(4):
                        if 0<=x+dx[k]<N and 0<=y+dy[k]<N:
                            if Map[x+dx[k]][y+dy[k]] == 1:
                                stack.append((x+dx[k],y+dy[k]))
            apts.append(apt)
print(len(apts))
apts.sort()
for apt in apts:
    print(apt)

그냥 주석을 안 추가한게 가독성에 영향 주는건가

📌 31575 도시와 비트코인

N,M=map(int,input().split())
dx,dy=[1,0],[0,1]
Map=[list(map(int,input().split())) for _ in range(M)]
stack=[(0,0)]
flag=False
while stack:
    x,y=stack.pop()
    Map[x][y]=0
    if x==(M-1) and y==(N-1):
        flag=True
        break
    for i in range(2):
        new_x, new_y = x+dx[i], y+dy[i]
        if 0<=new_x<M and 0<=new_y<N and Map[new_x][new_y]==1:
            stack.append((new_x,new_y))
if flag:
    print('Yes')
else:
    print('No')

이 문제 의외로 20분이나 잡아먹음.
진짜 말도 안되는 실수 계속 함.

if flag:
    print('Yes')
else:
    print('No')

이 부분을

print(flag)

이렇게 해놓고 왜 계속 틀리지?
로직이 뭔가 잘못됐나? 내가 잘못 읽었나?
이러고 있었음

문제가 요구하는 게 뭔지 꼭 생각해줄것.