반응형 [백준]214 [BaekJoon] 백준 4170번 불! 기존의 5427번 불 문제와 3055번 탈출 문제와 다른 점을 모르겠다. 이번 문제도 동일하게 풀었다. VISIT을 값에 따라 나눠준다. 0 : 지나갈 수 있다 1 : 지훈이의 방문 2 : 불의 방문 3 : 벽 지훈이 같은 경우에는, 1 2 3의 위치는 방문하지 않는다. 이미 지나온 곳은 방문할 수 없으며, 불은 갈 수 없고, 벽은 갈 수 없기에. 불 같은 경우에는, 2 3의 위치는 방문하지 않는다. 불이 지나온 곳은 방문할 수 없으며, 벽은 방문할 수 없기에. 중요한 핵심은 불의 위치들을 우선 큐에 먼저 전부 넣어준 뒤, 마지막으로 지훈이의 위치를 큐에 넣어준다. 그리고 bfs를 시작하면 된다. 그럼 한 사이클의 bfs만으로 문제를 풀 수 있다. "매 위치는 한 번만 방문하게 되고, 매 위치에서 고려는.. 2022. 7. 27. [BaekJoon/백준] 11559번 Puyo Puyo 문제를 읽고, 정의했다. 1 phase : 제거할 것 체크 한 뒤에 제거 + 중력 내리는 작업 dfs 함수를 돌면서, 인접 갯수가 4개가 넘는지 헤아린 뒤, 4개 넘으면 BBOM 함수(마찬가지로 dfs형식)를 통해 제거할 것으로 체크시킨다. 그 뒤에 for문으로 제거해주며 제거를 완료하면 중력으로 내리는 작업을 해준다. 내리는 작업은 맨 아래 행부터 체크하기 시작하며, 어디까지 내릴 수 있을지 체크하는 것도 맨 아래 행부터 체크하면 수월하다. /* 1 phase : 터지는 작업 + 내리는 작업 */ #include #include using namespace std; char MAP[12][6]; bool VISIT[12][6]; bool BOOM[12][6]; // 터질 곳 int mx[4] = {0,.. 2022. 7. 26. [BaekJoon/백준] 2206번 벽 부수고 이동하기 14923번 미로탈출 문제와 똑같은 문제다. BFS 한번으로 이 문제를 해결할 수 있다. 벽을 부순 상태에서의 이동 & 벽을 아직 부수지 않은 상태에서의 이동 두 가지를 갖고 계산해나가면 된다. 벽을 아직 부수지 않은 상태에서의 이동 VISIT[x][y][0]을 이용한다. 벽을 만나면, 벽을 부수고 이동하고 (VISIT[next_x][next_y][1] = VISIT[x][y][0] + 1) 벽을 만나지 않으면, 그냥 이동한다 (VISIT[next_x][next_y][0] = VISIT[x][y][0] + 1) 벽을 한번 부순 상태에서의 이동 VISIT[x][y][1]을 이용한다. 벽을 만나지 않으면, 그냥 이동한다 (VISIT[next_x][next_y][1] = VISIT[x][y][1] + 1) 벽.. 2022. 7. 25. [BaekJoon/백준] 2573번 빙산 반복문 + DFS SCC로 해결한 문제입니다. 크게 두 가지 섹션으로 나뉩니다. 반복문을 돌면서, 상하좌우 체크하며 녹아내릴 값을 계산합니다. SCC를 통해, 빙산 그룹이 총 몇개인지 체크합니다. 주의할 점이 두 가지가 있습니다. 1번을 실행할 때, 상하좌우 체크하며 녹아내릴 값을 계산한 직후, 빙산이 2에서 0이 되었다고 치면, 그 바로 옆에 있는 빙산을 계산할 때 문제가 생길 우려가 있습니다. ex) 0 0 0 0 2 3 => 2를 0으로 만든 뒤에 3을 고려할 때 2->0이 된 값도 고려할 우려가 있으므로, 처리를 한 빙산에 대해서는 VISIT 처리를 해줍니다. 모든 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력해야 합니다. /* for문 브포 + SCC */ #include #include u.. 2022. 7. 24. 이전 1 ··· 3 4 5 6 7 8 9 ··· 54 다음 반응형