본문 바로가기

BFS4

백준 1697 숨박꼭질 c++ 이번문제는 최단시간을 찾는것.수빈이가 움직일수있는건 현위치에서 1. 현위치 + 12. 현위치 - 13. 현위치 * 2 이걸 bfs로 풀면 아주 간단해진다. 먼저 위치의 범위를 초기화 해준다. 그 후 수빈이의 초기위치를 0으로 할당한다.(수빈이가 그 지점에 존재한게 0 초일때니까) 큐에 수빈이 초기 위치를 넣고 수빈이가 움직일수 있는 조건1~3 을 반복하면서 문제없으면 죄다 큐에 집어넣는다.수빈이 이덩위치가 동생위치 b이면 그때 그 지점에 할당된 숫자가 걸린 최단시간이다.먼저 수진이 무빙은 temp1~3으로 두고 한번 수진이가 도착한지점에 대해 3번 동작을 한다.for문을 돌며 0~100000 범위를 벗어나면 수빈이가 갈 수 없는곳이니 패스. (갔다는건 새로 큐에 넣겠다는것)그리고 새로 가는곳엔 현위치에서.. 2024. 10. 24.
백준 4179 불! c++ 이 문제를 보면 퍼져나가는 불이 있고 동시에 움직이는 J가 있다.J와 불 모두 사방으로 움직일 수 있다. J가 탈출하는 최단거리(탈출못할수도있음)를 구해야한다. 여기서 불도 퍼지고 J도 움직여야 하는데 이전에는 bfs로 풀때 큐를 이용했었다. 여기서도 마찬가지로 큐를 이용해서 한번 퍼질때 차례대로 집어넣고 움직인 요소들을 다시 큐에집어넣음으로써 확장시킨다.그러나, 사람(J)이 움직인건지 불이 퍼진건지 구분이 필요하다.그래서 입력값을 받을 board[][]를 준비하고불의 위치 추적을 위한 fire[][]도 준비하고사람이 방문한 위치 visit[][]도 준비한다. 사방면 이동 좌표변화량인 dx[] dy[]도 준비한다. 먼저 fire은 전부 0으로 초기화 해준다. 불이 퍼진곳은 1을 할당 할 것이다    me.. 2024. 10. 10.
백준 7576 토마토 c++ 이 문제를 읽어보면 마치 좀비바이러스 같다는 느낌을 받는다.어제의 아군이(안익은 친구) 오늘의 좀비가 되..(익어버림) 이번에는 M이 가로이고 N이 세로이다. 즉 m을 열로 제공한것. 헷갈리면 안됨.  그래서 이렇게 했다. 주요 사용 변수는board[][] //처음 인풋으로 초기상황 저장하는 변수visit[][] // 하루가 지날때마다 퍼져가는 상황 추적. 여기서는 방문 뿐만 아니라 며칠지났는지를 저장. date //전부 감염된 최솟값 저장.세가지이다. ps. dx,dy변수로 사방면 접근  https://ilovecomputerscience.tistory.com/entry/%EB%B0%B1%EC%A4%80-2178-%EB%AF%B8%EB%A1%9C-%ED%83%90%EC%83%89-C 백준 2178 미로.. 2024. 10. 8.
백준 2178 미로 탐색 C++ bfs로 풀 수 있는 문제이다.제한시간도 1초. 먼저 변수를int board[][];int visit[][];이렇게 둘것이다.애초에 우리는 0이 아닌 1만 지나갈것이기에 board를 0 또는 1로 초기화해준다.그리고 visit은 우리가 보드의 1 지점을 지났을때 이를 체크하기 위한 변수다. (지났는데 지난줄 모르고 또 지나면 아니되오) 또 int dx[], dy[]를 초기화 해줄것이다.특정지점 (a,b) 좌표가 있다고 하자. bfs는 기본적으로 한 지점에서 그 주위를 한번 쓱 훑는다. 자 그러면 이번문제에서 (a,b)기준으로는 사방면이 존재한다. 그렇다면 (a-1, b), (a,b-1),(a+1,b)(a,b+1)이렇게 4가지가 존재하겠다.이 행, 열 방향의 변화량을 각각 dx, dy로 둘것. 그래서  이.. 2024. 10. 7.

티스토리툴바