https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net bfs문제인데, 3차원 bfs문제이다. 즉 상하좌우 + 위 아래 방향도 탐색해주면 된다. 큐에는 기존에 x,y좌표만 넣었지만, 3차원이므로 x,y좌표와 몇 층인지 해당하는 정보를 넣어주면 된다. dist배열엔 토마토가 익는 시간을 저장해주면 된다. 만약 이 dist배열에 들어있는 값이 0보다 크다면, 이미 방문했던 (=토마토가 익어버린) 곳이라는 뜻이므로 굳이 탐색하지 않는..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 이 문제는 단순 bfs + 약간의 구현이라고 생각한다. 16509번 장군 문제를 풀고 오시면 뭔가 비슷한데..? 라고 느끼실 수 있다. 그러나! 이 문제의 요점은 바로 원숭이가 말(馬)처럼 K번 움직일 수 있다는 것이다. 때문에 주의할 점이 2가지 존재한다. 1. 한 점에서 탐색을 할 때 말처럼 움직일 수 있으면 말처럼 움직이고, 상하좌우 탐색도 같이 해줘야한다는 것! 2. 아래 ..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 오랜만에 푼 DP(다이나믹 프로그래밍)문제다. 우선 삼각형을 입력 받아준다. 입력값들의 길이가 1,2,3,... 순으로 증가하므로 2차원 벡터를 이용해 입력 받았다. 그런 다음, 초기값을 설정해주는 것이 중요한데 dp[1][0]은 삼각형의 맨 첫번째 값(=꼭대기 값)이고 dp[1][1]은 원래 존재하지 않는 값이지만 점화식을 생성 및 이용하기 위해 0으로 설정해주었다. 초기값(삼각형 1층)에 대한 설정이 끝났으므로, 그 아래 줄인 삼각형 2층부터 점화식을 이용해 최대값..
https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 이 문제는 얼핏 보면 아래 소스코드처럼 특정한 규칙을 찾아서 전부 탐색하여 배열을 돌려주면 풀릴 것 같지만, r의 입력이 최대 10억이므로, 10억번 반복을 하면 O(n)의 시간복잡도를 가질지라도 1초를 넘기게 되므로 시간초과가 뜬다! 해결 -> 덱(deque)에 넣어서 돌리자! 양파껍질까듯 바깥의 ..
https://www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 간단한 bfs 구현문제이다. 1. 상하좌우 중 한 방향으로 전진한다. 2. 전진한 방향 각각에 대해 대각선 탐색을 해준다. 3. 위쪽 방향은 {좌상, 우상}으로만 이동가능하고, 아래방향은 {좌하, 우하}로만 이동 가능하다. 왼쪽은 {좌상, 좌하}고 오른쪽은 {우상, 우하}다. 그게 바로 배열 dddx[]와 dddy[]이다! 해당 위치를 방문하였거나, 장기판 밖이 아닌 경우에만 큐에 좌표를 넣어주고 방문 처..
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 일반적인 다익스트라 알고리즘을 적용하면 된다. "다음 노드로 가는 가중치 + 현재 노드까지의 비용 < 다음 노드가 기존에 가지고 있던 비용" 이라면 다음 노드의 비용을 업데이트해주는 식으로 그래프를 탐색하면 된다. if(dist[now]!=cost) continue; if(dist[now] < cost) continue; // 동일한 코드! 중간에 이런 코드가 보일..
