본문 바로가기
반응형

[백준]214

[BaekJoon/백준] 5558번 Cheese 일본어로 된 문제다. 구글 번역기를 돌려서 해결하엿따 어렵게 생각할 필요 없는게, 그냥 숫자 순서대로 치즈를 먹으러 간다고 보면 된다. 같은 숫자는 없다는게 문제의 가정이다. S는 시작지점이고 X는 갈 수 없는 지점이다. 맵 내에서 숫자들을 만날 때 마다, 해당 숫자들을 저장해준 뒤 오름차순으로 정렬한 뒤 낮은 숫자부터 찾아가면 된다. 각 숫자를 찾아간 뒤에는 VISIT을 초기화해주는 것도 잊지 않는다. #include #include #include #include #include using namespace std; int N, M, K; char MAP[1000][1000]; int VISIT[1000][1000]; int SX, SY; vector CHEESSE; int mx[4] = {0, 0,.. 2022. 8. 4.
[BaekJoon/백준] 1600번 말이 되고픈 원숭이 오늘 원래 경사로 문제를 풀려고 했는데, 며칠째 붙잡아도 못 풀겠다. 진심 이게 왜 55퍼센트 정답률이지.. 난 돌대가린가. 어쩔 수 없이 다른 문제를 찾다가 이 문제를 풀게 되었다. 키포인트는 VISIT을 3차원 배열로 구성한 것이다. VISIT[z][x][y] : z는 말 움직임으로 움직인 횟수, x와 y는 좌표를 말한다. 이것만 활용하면 문제를 풀 수 있다. 나머지 코드 작성은 일반적인 bfs문제 코드 유형과 동일하다. #include #include using namespace std; int MAP[201][201]; int mx1[4] = {0, 0, -1, 1}; // 일반 움직임 int my1[4] = {1, -1, 0, 0}; // 일반 움직임 int mx2[8] = {-1, -2, -2.. 2022. 8. 3.
[BaekJoon/백준] 1520번 내리막 길 오늘 컨디션이 너무 안좋다. 세종병원에 심장진료를 받으려 예약하려 했는데, 아침부터 전화해서 연결해달라고 했는데 저녁될때까지 전화 남겨준다고만 하고 전화를 안줬다. 게다가 저녁이 다 되어서야 내일 전화준다고 한다 ㅎ.. 각설하고,, 이번 문제는 DP 문제이다. 1890번 점프 문제와 아주 유사한 문제이다. 위 링크에 나와있는 메모이제이션, 타뷸레이션 두 방법 중 메모이제이션 방법을 사용했다. 그리고 DP 정의는 아래와 같다. DP[x][y] = x,y 에서 목적지까지 가는 경로 수 내리막길이기 때문에, 역 경로는 존재하지 않으니 왔던길은 다시 돌아가지 않기에 우선 무한루프를 돌 가능성이 없다. => 1890번 유형과 결국 비슷하다. 상하좌우를 통해 모든 경우의 수를 구하되, 무한루프를 주의해야하는데, 기.. 2022. 8. 2.
[BaekJoon/백준] 16236번 아기 상어 동요를 떠올리게 해주는 문제 문제의 키포인트는 아래와 같다. 1. BFS를 통해, 다음으로 먹을 물고기 위치 탐색 2. 이동 후 먹은 뒤 반복 처음에는, 그냥 BFS 없이 2중 포문으로 연산하고, 거리를 맨헤튼 거리로 계산했었는데 이는 잘못된 방법이었다. 왜냐하면, 아기상어는 자신보다 큰 물고기가 위치한 곳으로는 갈 수 없기 때문이다. 주석을 아주 세세하게 달아놨는데, 흐름은 이렇다 a. 아기상어 시작 위치 저장 b. 아기상어 시작 위치에서 bfs를 돌면서, 먹을 수 있는 물고기들을 찾을 때 마다 {그곳까지의 거리, 맵에서의 절대적인 위치} 를 저장한다. 그곳까지의 거리는 초수계산을 위해 사용되고, 맵에서의 절대적인 위치는 우선순위를 따지기 위해 사용된다. c. 이를 토대로 cmp 비교함수로 정렬을 해준.. 2022. 8. 1.
반응형

티스토리툴바