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 이 문제.. 분명 맞게 푼 것 같은데 자꾸 시간초과가 나시는 분들이 있을 것이다. 아래 코드를 보자 if (nx = n || ny = m) continue; // 이미 방문한 경우 if (visited[nx][ny][wall]) continue; if (board[nx][ny] == 0) { q.push({nx,ny,ans..
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[]이다! 해당 위치를 방문하였거나, 장기판 밖이 아닌 경우에만 큐에 좌표를 넣어주고 방문 처..
