문제: www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 일차원 선 위에서 BFS를 이용하여 최단거리를 구하였다. 이때 수빈이와 동생의 위치는 0부터 100, 000까지이지만 수빈이는 현재 거리의 2배를 순간 이동할 수 있기 때문에 거리 배열을 100,000의 두배인 200,001로 선언하였다. 코드 #include #include using namespace std; int dist[200001]; int main(){ i..

문제: www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제풀이 BFS를 이용해 최단거리를 구하는 문제이다. 이 문제는 시작점(익은 토마토)이 여러 곳이므로 시작점을 모두 큐에 넣어준다. 코드 #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int board[1000][1000]; int dist[1000][1000]; int main(..

문제: www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제풀이 BFS를 이용해 (1, 1) 부터 (N, M) 까지의 최단거리를 구하는 문제이다. 미로가 공백없이 한 행씩 입력되므로 맵을 문자열로 선언했다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin>>N>>M; string board[100]; //한 행씩 입력되므로 문자열로 선..

문제: www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제풀이 BFS 알고리즘으로 문제를 풀었다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin>>n>>m; int visited[500][500] = {0,}; int board[500][500]; int dx[4] = {-1, 1, 0, 0}; int d..

문제: www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 문제풀이 스택을 이용한 괄호 쌍 맞추기 문제이다. 괄호 쌍이 맞지 않게 입력이 되었다면 '{'을 '}'으로 또는 '}'를 '{'으로 바꿔 짝을 맞추는 최소 연산 횟수를 구한다. } -> { : '}'이 입력되었을 때 스택이 비어있다면 실행 { -> } : 입력 종료 후 스택에 남아있는 '{'에 대하여 실행(괄호 짝수개가 입력되므로 스택 사이즈의 2분의 1) 코드 #include #include usi..

문제: www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제풀이 왼쪽부터 레이저를 만나면 현재까지의 쇠막대기 수(스택의 사이즈 -1 )를 결과값에 더해주고 쇠막대기의 끝에 도달하면 결과값에 1을 더해주었다. ( ( -> s.push(1) ( ) -> result += s.size() - 1 ) ) -> result++ 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); ci..