stonesy

해결방법최단 경로를 구해야하므로 BFS를 사용한다.이때, visited를 3차원으로 만들어야 한다. 더러운 칸을 방문하는 순서를 고려해야 하기 때문이다. → visited배열을 3차원으로 관리해야한다. → 비트마스킹을 사용해야 한다.그래프를 모두 순회했음에도 답을 구하지 못한 경우는 방문할 수 없는 더러운 칸이 존재하는 것이므로 -1를 출력한다.모두 방문: curD==((1방문 처리: curD | (1 코드import java.util.*;import java.io.*;// 396ms// BFS + 비트마스킹 + dppublic class Main_4991_G1_로봇청소기_BFS비트마스킹 { static int h,w; // w: 방의 가로크기, h: 방의 세로 크기 static char[][..

해결방법3차원 visited 배열이 문제 풀이의 핵심이라고 생각한다.visited[r][c][i]는 (r, c) 위치에 도달했을 때, 방향 i(상, 하, 좌, 우 중 하나)로 이동한 경우에 사용된 거울의 수이다. 이때, visited가 3차원이어야 하는 이유는 같은 (r,c)라도 레이저가 상,하,좌,우 어느쪽에서 들어왔는지에 따라 다음 위치로 이동할 때 필요한 거울의 수가 달라질 수 있기 때문이다.따라서 BFS + 3차원 방문처리를 통해 풀었고, O(W*H)로 풀 수 있다. 코드import java.util.*;import java.io.*;public class Main_6087_G3_레이저통신 { static int H,W; static char[][] map; static List point; st..