고동치는고동

문제 링크 : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net bfs를 이용한 탐색 문제이다 기존의 탐색에서 벽을 한번 부수고 이동할 수 있다는 조건이 붙었기 때문에 구현하는데 어려움이 생겼다 이럴경우 각 좌표까지 최단거리를 두가지 상황으로 정리하면 쉽게 풀 수 있다 1. 벽을 뚫지 않고 격자까지 이동한 경우 2. 벽을 한번 뚫고 격자까지 이동한 경우 1번의 경우 벽이 없는 길로 1을 갱신하거나 벽을 뚫으면서 2의 ..

문제 링크 : https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파� www.acmicpc.net 주난이가 점프를 할 때마다 주난이를 둘러싸고 있는 친구들의 벽이 사라진다 즉, 주난이가 한번 점프를 하면 자신부터 탐색을 시작해서 탐색 경계를 제한하는 친구들이 사라지는 것이다 구현 방법은 bfs든 dfs든 상관없다. 중요한 것은 주난이부터 탐색을 시작해서 친구를 만나면 그 친구는 이번 점프로 제거된다는 것이다. 또한 친구가 제거되었으면 거기서는 탐색을 중지하고 돌아와야..

문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 익은 토마토가 중심이 되어서 bfs탐색을 하는 문제이다 대충 그림으로 표현하자면 다음과 같다 검정색 테두리는 토마토들이 담긴 격자이고 빨간색 동그라미가 초기 익은 토마토이다 초기 익은 토마토에서부터 파란색 -> 초록색 순서대로 bfs탐색을 하면서 안익은 토마토가 범위 안에 들어오면 익게 하고 모든 토마토가 익을때 까지 계속 탐색하면 된다. 물론 bfs는 진행할 수 ..

문제 링크 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 1번부터 dfs를 돌며 탐색한 노드의 수를 세는 문제이다 #include // 인접행렬 int map[101][101] = { 0 }; // 노드를 방문했는지 저장하는 visit 배열 int visit[101] = { 0 }; int computer_num, ans = 0; // 감염된 사람을 전부 찾아내는 dfs void dfs(int n) { ans++; // dfs 한번 돌때마다..

문제 링크 : https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 격자상에서 dfs를 활용하여 푸는 문제이다 dfs를 사용하는 방식은 아래의 문제와 매우 유사하다 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u,..

문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 격자상의 그래프에서 bfs 탐색을 하는 문제이다 기존 bfs와 다른 점이라면 1. 그래프 이동을 격자상의 상하좌우로 한다. (dx, dy 배열) 2. 격자 한칸이 노드이므로 격자 정보가 x,y 두가지 정수로 다뤄진다 (node 구조체) #include #include #define n_ 100+5 using namespace std; int n, m; int arr[n_][n_]; int dp[n_][n_]; //..

문제 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 연결요소란 말 그대로 서로 연결되어 있는 요소의 개수이다. 이 그래프 같은 경우 한개의 그래프가 두개의 연결요소로 분리되어 있는 것이다 만약 두 연결요소를 간선을 통해 이었을 경우에는 그래프안의 연결요소가 하나로 통합된다 구현방법은 dfs를 기반으로 한다 1번부터 n번 노드까지 순회하며 탐색되지 않은 노드에서부터 df..

문제 링크 : https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저� www.acmicpc.net 백준에 있는 예제를 통해 막대 개수를 세는 알고리즘을 짜 보자 확실한 것은 막대기를 자르는 레이저가 최종 막대의 개수를 결정하는 요소라는 것이다 레이저가 막대기를 관통하는 것은 하나의 막대기가 두개로 분할되는 것이 아니라 하나의 막대기의 일정 부분을 잘라서 새로운 막대기를 만들어내는 것이다 결국 똑같은 말이지만 관점을 다르게 해야 쉽게 막대의 개수를 셀 수 있는 방법이 보인다 먼저 모든 막대..

문제 링크 : https://www.acmicpc.net/problem/9012 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)�� www.acmicpc.net 올바른 괄호 쌍 문자열을 하나 보자 ( ( ) ( ) ) ( ( ( ) ) ) VPS일 경우에 앞에 등장하는 작은 괄호쌍부터 하나씩 제거해 나갈 수 있다. ( ( ) ( ) ) ( ( ( ) ) ) ( ( ) ) ( ( ( ) ) ) ( ) ( ( ( ) ) ) ( ( ( ) ) ) ( ( ) ) ( ) 빨간색 괄호쌍은 제거되는 괄호쌍이다 사실 맨 ..

문제 링크 : https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 스택을 사용하는 문제이다. 막대기가 다음과 같을 때 6 9 7 6 4 6 오른쪽에서 보이는 막대기는 다음과 같다. 6 9 7 6 4 6 막대기가 다음과 같을 때는 9 10 8 2 4 5 3 1 오른쪽에서 보이는 막대기는 다음과 같다. 9 10 8 2 4 5 3 1 막대기가 오른쪽에서 보이는지 결정하는 조건은 딱 한가지이다. 오른쪽에 자신보다 큰 막대가 없으면 오른쪽에서 보이는 막대가 된다..