4179번: 불! (acmicpc.net) 미로에서 일하는 지훈이에게 미로에 불이나는 상황이 발생한다. 입력 첫줄에 미로의 행(R) / 미로의 열 (C) 가 주어진다. ' # ' - 벽 ' . ' - 지나갈 수 있는 공간 ' J ' - 지훈이의 초기 위치 ' F ' - 불이 난 공간 불은 매 분마다 한칸씩 네 방향(상,하,좌,우)으로 확산되며, 지훈이와 붙은 벽을 통과하지 못한다. 지훈이가 탈출 가능하다면 가장 빠른 탈출시간을, 탈출을 못하고 타죽는다면 IMPOSSIBLE을 출력하면 된다. #include #include #include using namespace std; //미로 string maze[1001]; //불이 옮겨가는 시간 int Ftime[1001][1001]; //지훈이가 이동하는 시..
BFS(Breadth First Search) 한 노드에서 시작해서 인접한 노드를 먼저 탐색하는 그래프 탐색 알고리즘이다. 코테에서는 다차원 배열에서 각 칸을 방문할 때 너비 우선으로 방문하는 알고리즘이라고 생각하면 된다. C++ STL - pair BFS 문제를 풀때는 Queue와 pair를 사용하기 때문에 pair를 알아두면 좋다. int main() { pair P; P = make_pair(3, 5); cout = width ? max : width; } } cout > m; //미로의 크기 //한줄로 입력받음 for (int i = 0; i > board[i]; //미로의 행을 순서대로 돌며 -1로 초기화 시켜줌 for (int j = 0; j < n; j++) fil..
수식의 괄호 쌍 많이 나오는 문제는 아닌거 같지만, 전에 봤던 코딩테스트에서 못풀었던 기억이 있어서 공부해봤다. ( ) ( ) ( ) 위와 같은 괄호가 있다면 잘 맞아떨어지는 올바른 괄호의 쌍이다. ( ) ) ( ) 위와 같은 괄호는 가운데 ' ) ' 때문에 쌍이 안맞기 때문에 올바르지 못한 괄호의 쌍이다. 이 문제는 가장 마지막에 담긴 원소랑 비교를 해야하기 때문에 스택을 사용하면 적합하다. 여는 괄호일때는 스택에 Push를 해서 담아주고, 닫는 괄호일때는 스택의 top을 확인해서 쌍이 맞는지 확인해주고 맞으면 Pop해주면 된다. 괄호 쌍이 틀린 조건들 1. 닫는 괄호를 만났는데 스택이 비어있는 경우 (여는 괄호가 앞에 없었다는 뜻) 2. 닫는 괄호를 만났는데 짝이 안맞는 경우( 닫는 괄호로 대괄호를 ..
덱(Deque) - 양쪽끝에서 삽입/삭제가 가능한 자료구조 - 큐,스택,덱을 합쳐서 Restricted Structure라고 부름. - Deque / Double Ended Queue라는 뜻을 가지고 있다. - 원소의 추가/제거 O(1) - 제일 앞/뒤의 원소 확인이 O(1) C++ STL - Deque Deque의 문서를 보면 앞쪽에 원소를 추가/제거 할 수 있다는 것만 빼면 Vector와 상당히 유사한것을 알 수 있다. 자료구조의 Deque은 앞/뒤가 아니면 확인이 불가능하지만 STL의 Deque는 인덱스로도 접근이 가능하다. C++ stl vector vs deque 를 검색하면 많은 글들이 나오니 차이점들은 나중에 파보기로 하고, 코테에서 Vector와 deque중에 어떤걸 쓸지 판단하는 기준은 ..
큐(Queue) - 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄수있는 자료구조 (FIFO : First In First Out, 은행에서 번호표를 뽑고 기다리리는 것을 생각하면 편함) -추가되는 곳은 Rear / 제거되는곳은 front - 원소의 추가/제거 O(1) - 제일 앞/뒤 원소확인 O(1) - 앞/뒤가 아닌 원소의 확인 변경x C++ STL - Queue C++의 STL에서도 역시 Queue를 제공한다. 코테에서는 따로 구현할 필요 없이 헤더파일을 포함시켜 사용하면 된다. int main() { queue Q; Q.push(2); // 원소 삽입 2 Q.push(3); // 원소 삽입 3 if (!Q.empty()) //큐가 비어있는지 확인 후 제일 앞의 원소(2) 출력 cout > n; ..
스택(Stack) - 끝에서만 원소를 넣거나 빼는 자료구조 - 먼저들어간 원소가 나중에 나옴 (FILO : First In Last Out / 프링글스 통을 생각하면 편함) - 최상단(top) 원소의 추가/제거/확인의 시간복잡도는 O(1) - 다른 원소의 확인/변경은 불가능함. STL - Stack #include #include using namespace std; int main(void) { stack myStack; //스택에 원소 1을 삽입 myStack.push(1); //스택에 원소가 있다면 최상단의 원소를 출력 if (!myStack.empty()) cout