기로에 서다

문제 https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 풀이 1. 우선 해야 하는 걸 간단하게 정리하자면 아래와 같습니다. 1. 게임 보드의 서로 인접한 빈 공간 좌표 집합들을 구합니다. 2...

문제 www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 풀이 1. 간단하게 생각해본다면 시작 점에서부터 BFS를 돌려 "왼쪽 위 점에서부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 확인하며 진행하면 될 것 같지만 $O(n*m*h*w)$로 시간 초과가 납니다. 2. "해당 점에서 부터 오른쪽 아래 점까지 1이 포함되어 있는가?"를 연산하며 중복된 칸을 계속 탐색하므로 이를 막기 위해 dp를 사용합니다. 이때 상태 정의는 "dp[i]..

문제 programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 1. 이동하는 비용에 대해서 살펴보면 다음 칸으로 이동할 때의 방향이 현재 칸으로 이동한 ..

문제 www.acmicpc.net/problem/5980 5980번: Corn Maze This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both www.acmicpc.net 문제 풀이 알파벳으로 입력받는 Transport해주는 점들의 좌표를 따로 관리해주며 그 점들 간의 이동시에는 0 코스트가 들기 때문에 방..

문제 www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 풀이 지나갈 수 있는 최소 값과 최대 값을 투포인터로 관리하며 시작점부터 bfs를 통해 끝점까지 가는 경우에 최대 값 - 최소 값을 갱신해준다면 $O(N^2*200)$으로 시간내에 답을 구할 수 있습니다. 코드 #include using namespace std; typedef pair pi; const int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,..

문제 www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 풀이 1. 빙하가 녹는 시간마다 BFS를 돌릴 때, 최악의 경우 $O(R*C*max(R,C))$로 TLE가 난다. 2. 이에 빙하가 녹는시간을 BFS 한번으로 전처리한 후, 빙하가 녹는 시간에 대한 백조의 이동을 줄여보기로 한다. 3. 백조가 만날 수 있는 최소시간이 T초일 때, T-1초엔 녹지않은 빙하때문에 만날 수 없다는 점에서 "시간이 T일 때 백조가 만날 수 있는 가?" 라는 결정함수..