문제 : https://www.acmicpc.net/problem/2636 풀이 공기와 접촉된 치즈는 매 턴마다 녹아 공기가 되는 문제이다. 이때, 중요한 점은 치즈로 둘러쌓인 공기 주변의 치즈는 녹지 않는다. 즉, 치즈를 녹일 수 있는 공기와 녹일 수 없는 공기를 별도로 분리하는게 핵심! 처음, 치즈를 녹일 수 있는 공기를 분리한다(배열에서 0->2로 변경) 그리고 본격적인 턴에 들어간다. bfs를 이용해 치즈를 녹일 수 있는 공기 주변 1칸에 있는 치즈들을 별도로 배열에 넣는다. 만약, 치즈를 녹일 수 있는 공기 주변에 치즈를 녹일 수 없는 공기가 있다면, 해당 공기를 0->2로 바꿔준다 이후, 녹을 예정인 치즈들을 공기(2)로 치환해준다. 이번턴에 몇개의 치즈가 녹았는지 계산해준다. 마지막으로, 몇번의 턴이 걸렸는지, 마지막 턴에 몇개의 치즈가 녹았는지 출력

문제 : https://www.acmicpc.net/problem/13549 풀이 일반적인 bfs가 아닌 0-1를 이용하는 문제이다. 0-1 bfs는 아래과정과 같이 진행된다 deque의 front(left)에서 현재노드를 꺼냄 연결된 인접 노드 탐색 해당 인접노드를 탐색할 수 있을 경우(이동가능한 경우) 해당 노드를 향하는 가중치가 0이면 덱의 front(left)에 삽입 해당 노드를 향하는 가중치가 1이면 덱의 back에 삽입 가중치가 가장 낮은 정점으로의 이동을 우선순위로 해야하므로 덱의 front에 삽입하게 된다. 일반 bfs와 동일하게 간선의 갯수(E)만큼 탐색, 정점의 갯수(V)만큼 중복없이 방문하므로 시간복잡도는 O(V+E)로 동일하다.

문제 : https://www.acmicpc.net/problem/13913 풀이 bfs(너비우선탐색)을 통해 해결하는 문제이다. N에서 k까지 주어진 3가지의 이동방법(N-1,N+1,N*2)를 통해 최단거리로 이동하면서, 그 이동횟수와 이동방법을 출력해야한다. 처음엔 dp를 이용해 풀려했지만, 시간초과가 날 것 같아서 pass! 먼저 이미 왔던 길인지 확인하기 위한 li배열과, 해당위치로 오기전 이전위치를 알기위한 move배열을 만든다. 그리고 bfs를 통해 N부터 시작한다. 만약 현재위치(x)가 K일 경우, li[x]를 출력하고 리턴 x-1, x+1, x*2의 방법중 0<=i<=100000이고 해당위치를 방문하지 않았다면(li[i]==0) deque에 추가한 뒤, move[i]=x(i번째 위치를 오기전에는 x위치) N이 K까지 도달할 수 없는 방법은 없으므로 예외는 생략한다.(N+1만 반복해도 도달하므로) res배열에 K를 추가한 뒤, x=K로 선언 x가

문제 풀이 4x4의 격자판에서, 임의의 한점에서 시작해 상하좌우로 7번 움직여서 만들어지는 문자열의 총 개수를 구하는 문제이다. 이때, 이미 들렀던 장소를 또 들러도 되는것이 중요! 4x4의 각 격자를 순회한다 한 격자에서 출발해, 상하좌우로 1번씩 움직이며 bfs를 순회한다. 이때, 이동한 위치가 격자밖을 나가면 안되며, 7번 다 움직일 경우 딕셔너리에 추가 딕셔너리로 중복된 문자열이 없게 체크! 최종적으로 딕셔너리의 길이를 리턴! 시간초과가 될 것 같았지만, 이풀이말고 크게 떠오르는게 없어서 해봤는데 다행이넹 ㅎ

문제 풀이 BFS를 이용했다. 서로를 알고 있는 두사람의 번호 A, B를 이차원 li 배열에 각각 넣어준다. li[A].append(B) li[B].append(A) 그리고 모든 정점을 순회하며 visit가 0(방문한적이 없으면)이면 bfs순회 시작 ** 아무도 모르는 사람이 존재할 경우, 그사람은 단독그룹이므로 bfs순회시 무조건적으로 tmp+=1 해주어야함.

N과, NXN의 이차원 배열이 주어진다. 이차원 배열은 1,2,3,,,,N의 숫자가 랜덤하게 들어있다. 이때, 어느 방 하나를 골랐을때 숫자가 A라면, 상하좌우에 A+1이 존재할 경우 해당방으로 이동하고, 이동을 할 수 없을때까지 이동했을때 이동한 횟수가 최대인 처음시작 방(A)과 이동횟수를 구한다. 방문처리할 필요가 없으므로 visit는 사용하지 않는다. 이차원 배열을 순회하면서 상하좌우에 lii+1의 값이 있을경우 count를 갱신 [이동횟수,처음시작방번호] 순회가 끝날때마다 결과값 갱신 이동횟수가 결과값보다 클경우 [이동횟수,방번호] 갱신 이동횟수가 결과값과 같고 방번호가 결과값의 방번호보다 작을경우 [이동횟수,방번호] 갱신

bfs 문제이다. 주어진 행렬(li)와 사이즈가 같은 2차원배열 visit을 만들어준다. 행렬을 순회하면서 visiti=0이고(방문하지않은곳), lii!=0이면 (i,j)을 deque에 넣어주고 size값을 갱신해준다. 대각선으로는 이동하지 않으므로, dx, dy설정에 유의 이때, size는 [들린횟수(크기),직사각형의 왼쪽위값(처음 방문할때의 값),직사각형의 오른쪽 아래값(마지막 방문할때의 값)] 처음 방문할때의 x,y가 직사각형의 왼쪽 위 값이고, 직사각형의 오른쪽 아래값은 계속 갱신해준다

swea, 1227번 미로문제를 응용하는 BFS문제이다. 기본적으로 bfs는 방문처리를 하는 visit배열과 주어진 list 배열 2가지를 이용하는데, 여기서는 효율성(최소복구비용)을 따져야 하므로 time 배열을 하나 추가했다. 즉, 아래에서 li배열 -> 해당 x,y지역을 복구하는데 드는 시간 time배열 -> 해당지역에 도착해 복구하는데 드는 최소 총 시간 v

swea 1226, 미로1에서 미로의 size가 16 -> 100으로 커진 버전이다. 똑같은 BFS 알고리즘으로 해결! (1,1)에서 출발해, 상하좌우를 탐색 (nx,ny)가 0일경우 방문처리 후 탐색 (nx,ny)가 3일경우 결과를 1로 바꾸고 break!

(1,1)에서 출발해, 도착지점까지 도달할 수 있는지 확인하는 문제이다. 기본적인 BFS문제! (1,1)에서 시작해, 상하좌우(dx,dy)를 탐색한다 (nx,ny)가 0일경우 이동하면서 방문처리한다. (nx,ny)가 3일경우, 결과값을 1로 바꾸고 break!