코린이 탈출기

문제 바로가기 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net Logic Algorithm: 시뮬레이션, BFS findDistance(taxi_y, taxi_x, passengerMap): BFS로 현재 택시 위치에서 승객의 위치까지의 그 승객의 index와 최소 거리를 return 하는 함수. 만약 최소 거리가 여러 개라면, 여러 개 모두 return passengerMap: 현재 승객들의 위치의 좌표를 저장하는 이차원 리스트(택시 탑승 완료된 승객은 표시 x) que..

Algorithm 유향 그래프의 정점을 정렬 정점을 오른쪽 방향으로 쭉 나열했을 때, 오른쪽에 있는 정점에서 왼쪽의 정점으로 이동하는 간선은 하나도 없도록 만듦 위상정렬 조건: 그래프가 DAG(Directed Acyclic Graph)의 형태를 띄어야함. -> 방향이 있고 싸이클이 없는 그래프 적용 그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈 수 있는 조건이 주어지는 경우 Ex) 줄 세우기를 하는데, 키가 작은 사람은 키가 큰 사람보다 무조건 앞에 서야함 Queue로 구현하기 들어오는 간선이 없는 (indegree가 0인) 정점을 모두 큐에 넣는다. 정점의 개수만큼 이를 반복한다. 2-1. 큐의 front를 pop해서 그 정점에서 나가는 간선을 모두 삭제한다. 2-2. 삭제하..

www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net Logic erase_set: 원판에서 지울 좌표를 저장하는 Set -> 중복 제거를 위해서! checkHorizontal(num): 원판의 가로라인에서 인접하면서 수가 같은 경우를 찾아서 erase_set에 저장한다. checkVertical(num): 원판의 세로라인에서 인접하면서 수가 같은 경우를 찾아서 erase_set에 저장한다. processAverage(): 원판 점수의 평균을 구하..

문제 바로가기 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net Logic 바이러스는 Virus 리스트에 담는다. 이 중 M개를 골라 조합을 만들고, activate_Virus에 담는다. 바이러스가 아직 안 퍼진 곳(즉, Map에서 0인 부분)의 count를 세어서 virus_count에 저장한다. 활성화 바이러스 조합 각각에 대하여 bfs(virus) 함수를 실행한다. 3-1. 활성화 바이러스를 queue에 넣는다. 3-2. 현재 queue에 들어있는 원소들에 대해서만 한다. -> level 을 계산해주기 위해서 3-3..

Logic low, high를 정한다. low가 high보다 작거나 같을 때까지 while문을 반복한다. while문 내에서 mid를 정한다. 탐색할 값이 mid보다 작다면 반틈으로 나눈 것 중에서 앞부분에 있다는 뜻이므로 high = mid - 1로 바꾼다. 탐색할 값이 mid보다 크다면 반틈으로 나눈 것 중에서 뒷부분에 있다는 뜻이므로 low = mid + 1로 바꾼다. 관련 문제 www.acmicpc.net/problem/2805 더보기 풀이보기 나무의 길이 최댓값이 매우 크기 때문에 그냥 구현하면 시간 초과가 발생한다. 이분탐색을 이용해서 절단기 높이 최댓값을 효율적으로 찾을 수 있다. low = 0, high = 1000000000(최대)로 정해두고, 이분탐색을 통해서 각 경우의 절단된 나무길이..

문제 바로가기 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com - info[][] 배열: 각 블럭에 부딪혔을 때 기존의 방향이 어떻게 달라지는 지를 저장하고 있음(key: 기존 방향, value: 새로운 방향 / 0: →, 1: ↓, 2: ←, 3: ↑) - warmHole 벡터: 각 warm hole의 (y, x) 쌍을 저장한다 1. 주어진 map의 바깥에 블럭 5를 한줄씩 더 만든다. (5의 모양이 ㅁ이므로 제일 가장자리를 만났을 때 방향을 꺾도록 하기 위해서) 2. map[y][x]가 0인 부분에서 네 가지 방향으로 모두 simulate 한다. in Simulate() 1. 현재 가진 방향으로 옮겨서 ny..

벽돌 깨기 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com crash(): 구슬이 벽돌이 깨뜨릴 때 호출되는 함수. 벽돌이 또 다른 벽돌을 깰 때도 호출됨 removeEmpty(): 벽돌이 다 깨진 후 사이사이의 빈공간을 없애주는 함수 -> 백트래킹으로 구현했음 1. possible 리스트에는 각 열에서 처음으로 깨질 행의 번호가 저장되어 있다. 2. 구슬을 쏠 수 있는 범위(0~W-1)만큼 crash -> removeEmpty를 한다. 다시 재귀로 호출 3. arr와 possibe 다시 원상태로 돌리기 4. 구슬을 쏠 수 있는 횟수만큼 다 쏘거나 그 전에 모든 벽돌이 깨진다면 solution() 종료 -전체 ..

문제 바로가기 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 시간: 2시간 처음에 잘못 생각해서 치즈 기준으로 bfs를 했다. 다시 푸느라 오래 걸렸다 ㅜㅜ 1. 치즈 안에 있는 구멍은 외부 공기와 접하지 않기 때문에 치즈와 바깥공기가 접하고 있는 부분을 찾아내야 한다. 이를 찾아내기 위해 가장자리부분과 인접한 모든 빈 공간을 bfs로 찾는다. 이때 치즈 안에 있는 공간은 당연히 찾아질 수 없다. 이렇게 찾아낸 부분은 visited에 저장한다. 2. visited에는 치즈인 부분(구멍포함)과 바깥부분 이렇게 나뉘게 된다...