공부일기장

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽부수고 이동하기 시리즈 다 풀고 백트래킹 해야겠다. "벽 부수고 이동하기 1" 문제를 처음 풀 당시의 코드가 완전 개판이어서, 2번을 풀 수 없었는데, 이번에 "벽 부수고 이동하기 1" 문제를 풀고 2번을 보니 코드를 잘 짜서 그런지 활용하여 풀 수 있을 것 같았다. 접근 방법 이전 문제에서 벽을 1개만 부술 수 있었는데, K개만큼 부술수 있게 되었다. 이전 ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs를 처음 배울때 이 문제를 어렵게 풀었던 기억이 나서, 다시 풀어보았다. 접근 방법 이 문제를 처음 풀때는, 모든 벽을 한번씩 만 부술 수 있으므로, 모든 벽을 한번씩 부숴보고 bfs를 돌렸었다. 결과는 당연히 TLE. 최소의 값을 찾는 문제이므로, (0,0)에서 bfs를 돌린다. 그리고 탐색하면서 만나는 벽을 한번씩 부숴보는 것이다. 큐에 넣을 때 현재 위치와 벽을..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 자바스크립트에 열중한다고 손놓던 백준을 다시...꾸준히 시작해야겠다. kks227 블로그 보면서 풀었던것들이랑, 안풀었던 것들 다시 풀면서 감 익히기. 접근방법 100개의 칸, 시작지점부터 목적지까지 도착하는 최소의 횟수. 문제의 분류가 그래프탐색인 걸 알고 있었지만, dp로 풀기에 너무 완벽한 조건이라 dp로 접근을 했다. "dp[idx] = idx..

https://www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net html 공부를 열심히 하다가 머리를 식히려고 들어간 백준이었으나 호되게 당해버린 문제. 알고리즘 공부는 무조건 꾸준히 하는걸로.. 접근방법 파도가 칠 때마다 모래성이 부서진다. 모래의 강도가 최대 9이므로, 모든 모래에 대해 완전탐색으로 풀려고 하였다. 더이상 모래가 부서지지 않을 때까지 O(1000*1000*@) 탐색을 돌렸는데, 당연히 시간초과를 받았다. 조금만 ..