백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (C++)

백준 2186번: 문자판 (C++)

접근 https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 처음에는 DFS 알고리즘을 이용하여 K칸 이동하는 식을 통해 문제를 해결하려 하였지만, 딱 봐도 시간초과일 것 같아 중복 계산을 막을 수 있는 방법을 찾기 시작하였다. 결과적으로는 DP[101][101][81]의 배열을 만들어 DP를 이용하여 풀 수 있었다. DP[a][b][c] = d 라고 할 때 이 의미는 MAP[a][b]에 있는 문자가 c번째로 쓰일..

2022. 5. 5. 21:55
코딩/백준 (C++)

백준 16946번: 벽 부수고 이동하기 4 (C++)

접근 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 입력을 받고 MAP을 순회하면서 0이 아닌 지점들에서 bfs 탐색을 진행한다. 인접한 0의 갯수를 카운트하면서 동시에 또다른 큐를 만들어 인접한 1들을 체크해주고 bfs 탐색이 완료되면 인접접한 1들(벽들)에 카운트한 숫자를 더해준다. 마지막으로 다시 MAP을 순회하면서 10으로 나누어 남는 나머지를 출력해준다. 코드 #include #include #include us..

2022. 5. 5. 16:41
코딩/백준 (C++)

백준 16954번: 움직이는 미로 탈출

접근 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 체스판의 크기가 8이므로, 벽이 총 8회 움직이고 나면 체스판에 벽이 사라지게 된다. 즉, 욱제가 8턴까지 벽에 맞지 않고 살아있다면 체스판을 탈출할 수 있다고 생각하고 dfs 알고리즘을 이용하여 풀이하였다. 추가적으로 벽의 좌표를 구조체로 만들어 총 8개의 배열에 저장(벽이 총 7번 이동할 때까지 욱제가 살아있으면 체스판 탈출 가능)해주었고, 욱제가 이동할때 해당하는 벽의 위치에..

2022. 5. 5. 13:12
코딩/백준 (C++)

백준 1981번: 배열에서 이동 (C++)

접근 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 이분탐색과 BFS 알고리즘을 이용하는 문제였다. 이분탐색을 통해 간격을 줄여가며 최대-최소 값이 될 수 있는 최소 값을 찾는다. 탐색하는 중에 해당 값으로 (1, 1) 에서 (N, N) 으로 도달할 수 있는지 탐색하는데 BFS 알고리즘을 이용한다. 처음에는 DFS 탐색을 통해 최대 최소값을 갱신해가면서 문제를 풀어보려고 했지만, 시간 초과로 문제를 해결할 수 없었다. ..

2022. 4. 30. 20:35
코딩/백준 (C++)

백준 1039번: 교환 (C++)

접근 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net C++을 하면서 처음으로 set을 이용해보았다. set이 중복되는 값을 입력받지 않는다는 점을 이용하여 아래의 문제 풀이에서 중복 체크하는데 사용하였다. 먼저 주어진 수를 string으로 바꿔서 문제를 풀이하였다. string의 경우 index를 이용하여 각 자리를 바꿀 때 간편하다는 점을 이용하기 위함이다. BFS 알고리즘을 이용하여 K회 자리 바꾸었을 때 가능한 모든 수를 탐색하여 그 수 중 가장 큰 수를 찾아내는 방법으로 문제를 해결하였다. string을 ..

2022. 4. 29. 00:57
코딩/백준 (C++)

백준 4991번: 로봇 청소기 (C++)

접근 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 간단하게 말하자면 트리(그래프)가 아닌 문제를 트리로 만들어서 풀면 쉽게 풀 수 있다. bfs 알고리즘을 이용하여 출발점과 각 쓰레기 위치까지의 이동 거리, 그리고 각 쓰레기 위치에서 다른 쓰레기 위치까지의 거리를 모두 측정하면, 각 쓰레기 위치를 노드로 하고 그 사이의 거리를 간선의 길이로 하는 그래프를 그릴 수 있다. 해당 그래프에서 모든 노드들을 방문하는 최소 간선의 길이를 가지는 경로를 dfs..

2022. 4. 28. 01:32
반응형