백준 2536 : 버스 갈아타기

https://www.acmicpc.net/problem/2536

2536번: 버스 갈아타기

https://github.com/HPYoo/swcodingtest/commit/054f976e716263d32f06218ae1d94793b3987f85

sw coding 2536 2nd update (Baekjoon) · HPYoo/swcodingtest@054f976

1. 그래프 만들기

 문제의 아이디어는 좌표 정보를 전부 받아서 그래프로 만들어서 풀어주는 것이다.

 그런데 그래프를 만들면 불필요하게 입력을 받는 경우가 생긴다. 경로가 겹치는 경우에는 큰 쪽 것만 차용한다. 경로가 작은 것을 선택해봤자 경로 범위가 넓은 것보다 경우의 수가 많아지게 되어 있으므로 생략한다.

 

2. 놓치지 말아야할 포인트

 -1) 경로 압축

 -2) 그래프 만들어주기

 -3) 배열 사용 자제!!

이 부분이 핵심. 메모리 제한이 256 MB 이다. 배열을 만들어 사용할 시 메모리 초과 메세지를 받고 틀리게 된다. 처음에 풀었을 때에는 배열을 만들어서 관리를 했었는데, 어떻게 해도 통과하지 못한다. 정수로 4 Byte의 메모리를 할당한다고 했을 때 버스 노선을 총 정리해서 모두 배열로 저장하면 메모리 제한을 가뿐히 넘겨버린다. 100,000 x 100,000 배열의 모든 노선 5000개가 존재한다면 모든 지점을 저장했을 때 최대 메모리는 8GB..? (계산이 맞는지는 모르겠다..) 문제 접근은 같았으나 효율면에서 구데기가 되어버린다. 고로... 메모리를 고려한 배열 사용 여부도 꼭 확인하고 넘어가자!

아래의 링크는 수정 전 코드https://github.com/HPYoo/swcodingtest/commit/24b9926dd287f7edac0375224d49d28b7959b8cd

sw coding 2536 update(Baekjoon) · HPYoo/swcodingtest@24b9926

 

3. 전체 코드(최종 수정)

 메모리 : 288894 KB, 시간 : 3324 ms (턱걸이), 푼 시간 : 2 + a (최초 풀이 오답 판정 이후 무한 수정...)

 다시 한 번 풀어봐야할 문제

m, n = map(int, input().split())
num_of_bus = int(input())
bus_info = {}
for _ in range(num_of_bus):
    temp = list(map(int, input().split()))
    bus_info[temp[0]] = [[min(temp[1], temp[3]), min(temp[2], temp[4])], [max(temp[1], temp[3]), max(temp[2], temp[4])]]
sx, sy, dx, dy = map(int, input().split())
graph = [[] for _ in range(num_of_bus + 1)]
check = [False] * (num_of_bus + 1)
# Find Bigger Bus Line
def find():
    for i in range(1, num_of_bus+1):
        temp = False
        x1, y1 = bus_info[i][0]
        x2, y2 = bus_info[i][1]
        for j in range(1, num_of_bus+1):
            if i != j :
                x3, y3 = bus_info[j][0]
                x4, y4 = bus_info[j][1]
                if x1 == x2 == x3 == x4 :
                    if y3 <= y1 <= y2 <= y4 :
                        temp = True
                if y1 == y2 == y3 == y4 :
                    if x3 <= x1 <= x2 <= x4 :
                        temp = True
        check[i] = temp
    for i in range(1, num_of_bus+1):
        if check[i] :
            continue
        x1, y1 = bus_info[i][0]
        x2, y2 = bus_info[i][1]
        for j in range(1, num_of_bus + 1):
            if check[j] : continue
            if i == j : continue
            x3, y3 = bus_info[j][0]
            x4, y4 = bus_info[j][1]
            if x1 <= x3 <= x2 and x1 <= x3 <= x2:
                if y3 <= y1 <= y4 and y3 <= y2 <= y4:
                    graph[i].append(j)
                    graph[j].append(i)
            # 한 점 혹은 겹치는 경우 (수평 방향)
            if y1 == y2 == y3 == y4:
                if not (x1 > x4 or x2 < x3):
                    graph[i].append(j)
                    graph[j].append(i)
            # 한 점 혹은 겹치는 경우 (수직 방향)
            if x1 == x2 == x3 == x4:
                if not (y1 > y4 or y2 < y3):
                    graph[i].append(j)
                    graph[j].append(i)
    return

def bfs():
    q = []
    a = []
    find()
    for i in range(1, num_of_bus+1):
        if check[i] :
            continue
        x1, y1 = bus_info[i][0]
        x2, y2 = bus_info[i][1]
        if x1 <= sx <= x2 and y1 <= sy <= y2 :
            q.append(i)
        if x1 <= dx <= x2 and y1 <= dy <= y2 :
            a.append(i)
    minValue = 1e9
    visited = [-1 for _ in range(num_of_bus + 1)]
    real_q = []
    for i in q :
        real_q.append(i)
        visited[i] = 0
    while real_q :
        x = real_q[0]
        del real_q[0]
        for i in graph[x]:
            if visited[i] == -1:
                visited[i] = visited[x] + 1
                real_q.append(i)
    for i in a :
        minValue = min(visited[i], minValue)
    return minValue+1

print(bfs())