개발기록 개발기록

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 문제입니다. 단순하게 하나하나 구현한다면 복붙한다해도 시간이 걸릴 것 입니다. 보통 이런 문제들은 생각을 살짝 바꾼다면 하나의 모듈에 여러 상황을 담을 수 있습니다. 행 오른쪽 경사로 탐색, 행 왼쪽 경사로 탐색, 열 위쪽 경사로 탐색, 열 아래쪽 경사로 탐색 문제에서 고려해야 할 상황입니다. 행과 열은 회전만 시켜주면 똑같은 것이고 오른쪽, 왼쪽은 뒤집으면 똑같은 것 입니다. 즉, 전처리로 저렇게 해주면 탐..

https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4= n || tb.y = n || tb.x = n || tc.y = n || tc.x = n) continue; if (visit[tb.y][tb.x][ts] || map[ta.y][ta.x] == 1 || map[tb.y][tb.x] == 1 || map[tc.y][tc.x] == 1) continue; q.push({ ta, tb, tc, ts, time + 1 }); visit[tb.y][tb.x][ts] = true; } } return -1; } int ..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 자연수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. www.acmicpc.net bfs 문제 입니다. 전형적인 문제와 조금 다른 점이 있습니다. 원숭이가 같은 (y, x) 라는 좌표에 있더라도 능력이 몇 번 남았느냐에 따라 남은 결과가 달라진다는 것 입니다. (y, x)에서 능력이 1번 남았을 때와 0번 남았을 때를 비교..

https://www.acmicpc.net/problem/16397 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 만들어야 하는 수를 뜻한다. www.acmicpc.net 완전탐색 문제입니다. 최단시간이므로 bfs가 좋을 거 같습니다. 다이어트를 조금 할 수 있을 거 같군요. 전에 만들어진 숫자에 대해서는 결과가 똑같기 때문에 굳이 볼 필요가 없습니다. 따라서 중복체크를 해줍니다. #include #include #include #include using namespace std;..

https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 전형적인 bfs문제입니다. 물이 퍼질 곳은 고슴도치가 갈 수 없다고 했습니다. 말 그대로 구현하면 조금 어려울 것 같습니다. 한 타임에 물,..

https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다. www.acmicpc.net 싸이클을 어떻게 찾을지가 관건인 문제입니다. bfs로는 불가능합니다. = 2) { cycle[cur] = true; return; } visit[cur] = true; for (int i = 0; i < dist[cur].size(); i++) { int next = dist[cur][..

https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 www.acmicpc.net 탈출은 무조건 배열 가장 바깥쪽에서 일어납니다. 그럼 역으로 따라가면 어떤 좌표들이 탈출할 수 있는지 알 수 있겠죠. dp로도 풀..

https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다. 두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자. www.acmicpc.net 특별 도시 사이에는 텔레포트가 가능합니다. 텔레포트가 직접 걸어서 가는 것보다 무조건 빠른 것은 아닙니다. 그러므로 직접 비교해봐야합니다. 따라서 다음과 같은 경우가 발생합니다. 1. 일반 -> 일반 1-1. 걸어간다 1..