떠혀니의 노오력

안녕하세요 !!! 우디😎입니다.오늘은 BFS로 푼 구슬 탈출 2 문제에 대해 설명해드릴께요. 문제[백준 13460] 구슬탈출 2 바로가기 문제 설명최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다. ==> 10번 동안의 BFS파란 구슬이 구멍에 들어가면 실패 , 기울이는 동작은 구슬의 움직임이 없을 때까지 기울임. (백준 예제 7번) ==> (빨간 구슬과 파란 구슬이 동시에 들어갈 수 있음) 😘 : 위의 KEY POINT 대로 차근차근 설명해드리겠습니다. ➊. 10번 동안의 BFS 빨간 구슬이 구멍을 찾아가기 위해서 상,하,좌,우 중 10개의 방향을 조합해서 찾을 ..

안녕하세요 !!! 우디🙇입니다.오늘은 BFS로 푼 테트로미노 문제에 대해 설명해드릴께요. 문제[백준 14500] 테트로미노 문제 설명 1. 테트로미노 모든 모양(좌우대칭)을 종이에 하나 하나 적재해서 최댓값 구하기.처음에 생각해낸 방법이 노가다 방법이었습니다. (직접 해보진 않았지만 ,,,) 시간 복잡도 빅오로 계산해보았을 때 500 X 500 X (8 X 5) = 10,000,000 (천만)500 X 500 개의 정사각형마다 테트로미노를 놓아야 되고 테트로미노 5종류 중에 좌우대칭한 모양이 각 종류마다 대충 최대 8개 있다고 하면 저렇게 계산이 되쥬 ? 이 문제의 시간 제한이 2초 (1초를 대충 1억번의 연산으로 생각) 이니깐 시간제한에도 안걸릴 것 같고 엄청난 정성이 있다면 이 방법도 괜찮은 것 같습..

안녕하세요 !!! 우디🤓 입니다.오늘은 DFS로 푸는 퇴사 문제를 설명해드릴께요 ~ 문제[백준 14501] 퇴사 문제 설명퇴사 전까지 겹치지 않게 상담을 하면서 최대 수익을 만들어야 합니다. 그러면, 최대 수익을 만들기 위해 최적화로 한번에 똬 !!!상담 일정을 잡을 수 있을까요 ?! 🐿️ : 저는 못할 것 같아요 ~! 녜녜 ~ 저도 그렇게 생각합니다 ! 그래서 이 문제는 상담일이 겹치지 않게 가능한 경우의 수를 모두 찾은 다음 (순환 DFS 사용)각 경우의 수의 최댓값을 계속 갱신해주면 됩니다 . (새로운 상담일마다 최댓값 갱신)우선, 상담일이 겹치지 않게 가능한 경우의 수를 트리🌳로 나타내면. 이렇게 되는데 이런 경우의 수를 구하는 방식을 저는 순환구조의 DFS 로 해결하였습니다.위의 예로 간단히 설..

안녕하세요 !!! 우디 ✨ 입니다 .오늘은 DFS 로 푸는 2048(Easy) 을 설명해드릴께요 ~ 문제BOJ 12100번 2048(Easy) 바로가기 문제 설명이 문제의 핵심은DFS로 순환구조 잡기상 하 좌 우 옮기는 작업이 두가지만 기억하고 문제를 풀면 됩니다 ! (말로는 참 간단하죠 ,,?^^)우선, 이 문제가 왜 DFS 로 접근해야 하는지 설명해드리겠습니다.xxxxxxxxxx보드를 최대 5번까지 움직일 수 있고, 움직이는 방향은 상,하,좌,우 총 4가지 입니다. 따라서 5번 동안 상,하,좌,우 이 4방향을 중복이 가능하게 나열을 해야합니다. (또한, 최대 5번 이므로 1번을 움직여서 최대가 나올 수 있고 2번을 움직여서 최대가 나올 수 있는 등 예측하지 못하기 때문에 한번 이동했을 때마다 전체 배..

안녕하세요 !!! 우디 입니다 ~ 이번에는 BFS 로 푸는 파이프 옮기기에 대해서 설명해 드릴께요. 문제 설명 이 문제는 모든 경우를 다 살펴봐야 합니다. 우선 파이프가 가로 방향일 때 -> 가로 or 대각선 으로 이동 가능 세로 방향일 때 -> 세로 or 대각선 으로 이동 가능 대각선 방향일 때 -> 가로 or 세로 or 대각선 으로 이동 가능 위 처럼 각 방향마다 이동 반경이 정해져 있고, 시작은 무조건 가로 방향부터 시작하니 아래 트리처럼 나타낼 수 있습니다. 이렇게 트리 형식으로 가로로 계속 경우의 수를 늘리다 보면 최종 (N,N)에 도착할 때 마다 갯수를 세어주면 되므로 이 문제는 그래프 탐색 기법의 큐를 기반으로 한 BFS 로 풀면 됩니다. 구현 저는 큐를 2개 사용해 주었습니다. 하나는 파이..