[PS][Java] java DFS & BFS
DFS와BFS
코드
java로 구현한 코드는 여기에 있습니다.
토마토
풀이
dx dy를 사용한 bfs 방법에서 dh까지 추가해서 진행합니다.
코드
java로 구현한 코드는 여기에 있습니다.
적록색약
풀이
R와 G를 같은 값으로 가지는 map을 하나 더 만듭니다.
코드
java로 구현한 코드는 여기에 있습니다.
탈출
풀이
물 -> 고슴 -> 물 -> 고슴 순서대로 1step 씩 진행 할 때, 물과 고슴도치 모두에 대해서 q의 size만큼 “q에서 꺼내서 step 진행”을 반복해야합니다.
코드
java로 구현한 코드는 여기에 있습니다.
벽 부수고 이동하기
풀이
다음에 방문할 칸이 0인 경우, 현재까지 부순 벽의 수를 curr.b는 0 또는 1일 수 있습니다. 0인 경우에만 처리하면 안됩니다.
코드
java로 구현한 코드는 여기에 있습니다.
벽 부수고 이동하기2
풀이
K개까지 벽을 부술 수 있는 경우 map의 3번째 차원은 k+1까지 생성해야 합니다.
코드
java로 구현한 코드는 여기에 있습니다.
벽 부수고 이동하기3
풀이
0으로 이동/ 대기 / 부수고 1로 이동을 따로 처리합니다. 대기하는 경우는 현재 위치, 현재까지 부순 벽의 수는 변함이 없고 낮/밤만 바뀌어서 다시 q에 들어갑니다.
코드
java로 구현한 코드는 여기에 있습니다.
벽 부수고 이동하기4
풀이
- tc : 아래 예시의 경우 9가 출력되어야 합니다. (1+8+8+8+8) %10은 3을 출력합니다.
3 3 000 010 000 - 시간초과 : 먼저 0을 기준으로 연결요소를 묶고 연결요소 안의 요수 갯수를 구합니다. 그리고 1 주변의 0이 포함된 연결요소의 총 갯수를 구할 때 이전에 구해놓은 갯수를 사용해야합니다. bfs를 수행하면서 0이 저장된 칸이 몇 번째 연결요소에 포함된 칸인지 저장합니다. 그리고 각 연결요소의 갯수를 저장해둡니다. 1 주변의 연결요소의 번호를 set에 넣고 iter로 순회하면서 중복된 연결요소의 경우는(위 1번 풀이 예시) 한 번만 더합니다.
코드
java로 구현한 코드는 여기에 있습니다.
연구소
풀이
2차원 백트래킹과 BFS를 사용합니다.
코드
java로 구현한 코드는 여기에 있습니다.
연구소2
풀이
1차원 백트래킹과 BFS를 사용합니다.
코드
java로 구현한 코드는 여기에 있습니다.
연구소3
풀이
map을 입력받으면서 모든 2의 좌표를 배열에 저장합니다. 그리고 이 배열의 idx에 대해서 1차원 백트래킹을 진행하면서 어떤 좌표의 2를 활성화시킬지 선택합니다. 활성화시킬 2가 선택되면 bfs를 진행합니다. bfs를 진행하다가 비활성화된 2를 만나는 경우에는 그 좌표를 q에 넣고 bfs를 진행하면 됩니다.
map이 0,1,2로 이루어졌기 때문에 몇 초 뒤에 도착하는지 map에 적을 때는 3부터 적습니다. 만약 bfs를 진행하고 mapd 저장된 수 중 가장 큰 수가 7이라면 4초만에 도착한 것으로 이해할 수 있습니다.
그런데 왜 아래 링크의 코드에서는 -2를 진행할까요?
입력 :
3 1
2 0 1
0 0 0
1 0 0
이동한 거리 :
2 3 1
3 4 5
1 5 6
활성화된 바이러스 다음 칸을 거리 3으로 하기 때문에 -2를 해야 적절한 답을 구할 수 있습니다.
코드
java로 구현한 코드는 여기에 있습니다.