문제 링크 https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net ◆문제 해결 및 설명◆ 문제 해설 : 생략 말이 좀 어려워서 애를 먹었는데(잘못된거 같기도) 예제를 보면 주난이와 이어진 0들의의 상하좌우를 0으로 만들어준다. 입력 예제 1번을 그림을 통해 표현해 보았다. 3번뛰면 (0,1)이 지워지면서 정답임을 알 수 있다. 일단, 교실의 정보를 저장할 변수 mapS과 위치정보(y10, x1, y2, x2)를 저장하고, 교실의 입력이 문자..
문제 링크 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 오늘의 생각 : 0 - 1 bfs를 배웠다. ◆문제 해결 및 설명◆ 문제 해설 : 0초가 걸리는 *2 순간이동과 1초가 걸리는 좌우1칸 이동을 통해 가장 빠르게 목적지(동생)에게 도착하자. 최단거리 문제중 가중치가 0또는 1이므로 다익스트라를 통해 풀 수 있겠다는 것을 알았지만, 최근 배운 0 - 1 bfs를 사용해 풀어보았다. 0 - 1 bfs는 ..
문제 링크 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 오늘의 생각 : 문제를 잘 읽자! ◆문제 해결 및 설명◆ 문제 해설 : 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다. 문제는 격자 내에 산봉우리의 개수가 ..
문제 링크 https://www.acmicpc.net/problem/1987 오늘의 생각 : 시간 초과가 날때, 백트래킹 기준이 안보이면 방식을 바꿔보자. ◆문제 해결 및 설명◆ 문제 해설 : 알파벳이 써있는 맵위 (0,0) 위치에서 출발하여 상하좌우로 움직일때, 새로 이동한 칸은 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 할때 최장거리를 구하여라 처음에는 맵을 나타내는 이차원 배열 map의 크기와 같게 visited 배열을 선언하고 못 가는 곳을 1로 설정해 dfs로 구현하였으나, 시간 초과로 인하여 visited를 일차원 배열로 설정 하였다. ◆코드 전문◆ #include #include #include using namespace std; int R, C, answer = 0; vector..
