BFS

자바(Java) 알고리즘 문제풀이 가장 먼 노드 찾기 [프로그래머스 / BFS]

문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예시 n vert..

자바(Java) 알고리즘 문제풀이 미로탈출 [이코테 / BFS]

문제 설명 동빈이는 N * M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 반씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴몰이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 떄는 시작과 마지막 칸을 모두 포함해 계산한다. 입력 조건 첫 번째 줄에 두 정수 N,M (4= 0 && nx < n && ny < m && map[nx][ny] == 1 && !checked[nx][ny]) { checked[nx][ny] = true; q.offer(..

자바(Java) 알고리즘 문제풀이 토마토 [인프런 / BFS]

강의의 문제를 가져왔기 때문에 밝힙니다 ! 임의로 추가, 수정, 삭제한 내용들이 있으니 정확한 이해를 위해서는 강의를 구매하시는 것을 추천드립니다 😅 출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 (인프런 강의) 풀이 코드 BFS 활용문제로, 토마토가 다 익는데 최소 몇일이 걸리는지 구하는 문제이다. 익은 토마토 기준으로 퍼져나가면서 주위의 토마토가 익는데, 최초에 익은 토마토가 한 개가 아니기 때문에 BFS 함수 호출 전, 미리 큐에 익은 토마토의 좌표를 넣어줘야 한다. 이 때문에 큐를 static 변수로 선언. 그러고 방향 벡터에서 상,하,좌,우 로 익지 않은 토마토를 발견하면 이동하면서 익은 토마토로 변경하고 익는데 걸리는 날짜를 좌표로 표현한 dis[][] 배열의 똑같은 좌표에도 ..