BOJ
BFS 기본 틀
BFS는 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. BFS에 대해서는 자료구조와 알고리즘 시간에 배웠으므로, 개념에 대한 자세한 정리는 따로 하지 않겠다. BFS를 구현하는 기본 틀은 아래와 같다. 반복 숙달을 통하여 자기것으로 만드는 것이 좋다. #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502] bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장 int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미 int main(void){ queue q; vis[0][0] = 1; //..
[C++] BOJ 2493 / stack 과 pair의 사용
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 스택을 사용하는 문제를 풀던 중 만난 문제였다. PS에 대한 경험이 적다보니, 손 가는 대로 코드를 짰고 그 결과 시간초과가 발생하였다. 처음 구현했던 방법은 Stack 3개를 써서 구현한 방식이었다. 시간을 단축하기 위해서 타워의 높이를 일괄적으로 스택에 넣고 POP 하며 계산하는 것이 아닌, 높이를 하나씩 push 받으면서 계산을 해야한다는 생각이 들었다. 첫 번째 시도에서는 놓쳤던 이 문제..