목록벽 부수고 이동하기 C++ (3)

1일1알

백준 14442번 벽 부수고 이동하기 2 C++

bfs #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m, k; int dRow[4] = { -1,0,1,0 }; int dCol[4] = { 0,1,0,-1 }; struct Info { int row; int col; int breakCnt; int moveCnt; }; vector board; vector found; int main() { ios_base::sync_with_std..
알고리즘 2022. 9. 21. 10:00
백준 16946번 벽 부수고 이동하기 4 C++

벽이 있는 위치에서 상하좌우를 검사하면서 빈 공간이 얼마나 이어져있는지 구해야 한다. 그런데 매번 bfs로 검사하면 시간이 오래 걸리기 때문에 한번 방문해서 이어진 곳은 따로 표시를 해둬서 다음번에 방문할때는 표시해둔 값만 더해주면 된다. 그리고 주의해야할점이 하나 더 있는데, 만약 벽에서 위쪽 빈공간과 오른쪽 빈공간이 이어져있다면 거리를 두번 더하기 때문에 이 부분을 잘 처리해야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = ..
알고리즘 2022. 7. 23. 16:04
백준 2206번 벽 부수고 이동하기 C++

동일한 지점에 늦게 도착하더라도 벽을 부술 수 있는 기회가 남아있으면 벽을 부수지 못하는 먼저 도착한 경우보다 먼저 목적지까지 도달할 수 있기 때문에 방문 여부를 기록하는 배열을 벽을 부술 수 있는 상태에서 방문한 것과 부수지 못하는 상태에서 방문한 것 두 가지로 나눠서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; struct Info { int row; int col; int dist; int chance; }; int dRow[..
알고리즘 2022. 2. 28. 12:05
이전 Prev 1 Next 다음