문제 링크 https://www.acmicpc.net/problem/10026 문제 해설 Idea 모든 방문하지 않은 칸에 대해 BFS 탐색하면서 같은 구역을 방문 적록색약의 경우 R과 G를 같은 구역으로 판단하고 탐색 각각의 경우에 대한 BFS 호출 횟수를 서로 다른 구역의 수로 판단하여 출력 Time Complexity BFS: O(N^2) = 10,000 Data Size N: 1 <= int <= 100 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/21758 문제 해설 Idea 벌이 같은 방향을 향하는 경우 상자까지의 총합에서 두 벌의 시작 위치에 있는 값을 제외 벌이 다른 방향을 향하는 경우 상자까지의 총합에 절댓값을 취해서 더함 Data Size N: 3 <= int <= 100,000 arr[i]: 1 <= int <= 10,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 N = int(input()) arr = list(map(int, input().split())) forward, backward = [arr[0]]+[0]*(N-1), [0]*(N-1)+[arr[-1]] for i in range(1,N): forward[i] = forward[i-1] + arr[i] backward[N-i-1] = backward[N-i] + arr[N-i-1] answer = 0 for i in range(1,N-1): answer = max(answer, forward[N-1]*2-forward[0]-forward[i-1]-arr[i]*2) answer = max(answer, backward[0]*2-backward[N-1]-backward[N-i]-arr[N-i-1]*2) answer = max(answer, forward[i]-arr[0]+backward[i]-arr[-1]) print(answer)
문제 링크 https://www.acmicpc.net/problem/5547 문제 해설 Idea 전체 좌표 평면의 외곽에 1만큼의 여백을 추가하고 x,y 좌표가 0부터 시작한다고 판단 y가 홀수 일 때, 인접한 좌표는 상하좌우와 함께 우상단,우하단을 포함 y가 짝수 일 때, 인접한 좌표는 상하좌우와 함께 좌상단, 좌하단을 포함 건물이 없는 좌표를 BFS 탐색하면서 건물과 만나는 지점을 카운트 Time Complexity BFS: O(N^2) = 10,000 Data Size W, H: 1 <= int <= 100 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 from collections import deque import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/7569 문제 해설 Idea BFS 7569번 토마토 문제에서 하나의 차원이 추가된 버전입니다. 차원이 늘어난만큼 N의 최대 길이가 감소했기 때문에 여전히 BFS로 해결할 수 있습니다. 익은 토마토의 기준에서 전체 상자를 BFS로 완전탐색하면서 안익은 토마토까지의 최소 거리를 기록합니다. 최소 거리의 최댓값이 곧 토마토들이 모두 익는 최소 일수이며, 모든 토마토가 다 익었을 경우에 최소 일수를 출력하고, 그렇지 않은 경우엔 -1을 출력합니다. Time Complexity O(N^3) = 1,000,000 Data Size M,N: 2 <= int <= 100 H: 1 <= int <= 100 t in [1,0,-1] 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 from collections import deque import sys input = sys....
문제 링크 https://www.acmicpc.net/problem/7576 문제 해설 Idea BFS를 활용한 시뮬레이션을 통해 모든 토마토가 익을 떄까지 걸리는 최소 기간을 계산 초기엔 안익은 토마토의 기준에서 매번 익은 토마토까지의 최단거리를 탐색하여, O(N^4)의 시간 복잡도로 시간 초과가 발생 이후 익은 토마토의 기준에서 시뮬레이션을 단 한번만 수행하여 각각의 칸에 도달하는데 걸리는 거리값을 갱신 모두 익지 못하는 상황에 대해 1안에선 에러를 발생시켜 처리했고, 2안에선 종료 코드를 실행해 처리 Time Complexity O(N^2) = 1,000,000 Data Size M,N: 2 <= int <= 1,000 t in [1,0,-1] 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 from collections import deque import sys input = sys....