백준 16933번 벽 부수고 이동하기 3 - C++ 풀이
1. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 2. BFS로 {1, 1, 0, 낮}인 상황 노드에서 {N, M, ?, ?}인 상황으로 가는 최단 거리를 구한다. 1. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 어떤 상황을 나타내기 위해 필요한 값은 {행, 열, 벽 부순 횟수, 낮밤여부}이다. 2. BFS로 {1, 1, 0, 낮}인 상황 노드에서 {N, M, ?, ?}인 상황으로 가는 최단 거리를 구한다. BFS를 사용해서 시작 상황에서 종료 상황까지 가는 최단 거리를 구할 수 있다. 각 노드에서 인접 노드는 상, 하, 좌, 우로 이동하는 경우 + 해당 칸에서 가만히 머무는 경우 총 5가지가 된다. 이때 인접 노드가 벽이라..
2022. 6. 16.
백준 1194번 달이 차오른다, 가자. - C++ 풀이
1. 열쇠 소지 현황을 비트 마스크 keys로 나타낸다. 2. (r, c) 위치에서 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다. 3. BFS로 탈출 상황까지 가는 최단 이동 횟수를 구한다. 1. 열쇠 소지 현황을 비트마스크 keys로 나타낸다. BFS에서 방문 여부를 배열로 기록하기 쉽게 하기 위해서 열쇠 소지 현황을 비트 마스크를 이용해서 나타내 준다. 2. (r, c) 위치에서 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다. 어떠한 상황을 나타내는 데 필요한 값은 위치와 열쇠 소지 현황이다. (r, c) 위치에서 비트 마스크로 나타낸 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다. 3. BFS로 탈출 ..
2022. 6. 15.
백준 2169번 로봇 조종하기 - C++ 풀이
1. dp(r, c, before): 이전 칸이 before이고 현재 (r, c)일 때, (N, M)으로 가면서 얻을 수 있는 가치의 최대 합 2. dp(r, c, before) = board[r][c] + max(dp(r+1, c, UP), dp(r, c-1, RIGHT), dp(r, c+1, LEFT)) 1. dp(r, c, before): 이전 칸이 before이고 현재 (r, c)일 때, (N, M)으로 가면서 얻을 수 있는 가치의 최대 합 dp(r, c, before)를 위와 같이 정의하자. 아래, 왼쪽, 오른쪽으로만 이동할 수 있으므로 before는 위, 왼쪽, 오른쪽 중 하나가 된다. 2. dp(r, c, before) = board[r][c] + max(dp(r+1, c, UP), dp(r..
2022. 6. 14.
