연향동큰손

문제 이해 그래프 문제들은 기본적인 틀을 벗어나지 않는 것 같다.DFS, BFS만 구현을 잘 한다면 그래프 문제를 보다 쉽게 풀 수 있을 것 같다는 생각이 든다.   이 문제는 전에 풀었던 2178번 미로 탐색 문제와 매우 유사한 느낌이다.https://www.acmicpc.net/problem/2178 다만 차이점이라고 하면 이번 문제는 이동 방법을 더 고민 해봐야 한다는 점이다. 이동 방법1) X축으로 2 or -2만큼 이동한 경우 ==> Y축으로 -1 or 1만큼 이동 2) X축으로 -1 or 1만큼 이동한 경우 ==> Y축으로 -2 or 2만큼 이동 이러한 규칙을 수행하기 위해 이번에는 dx dy 배열이 더욱 길어졌다static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2..

문제 이해 N x M 크기의 그래프가 주어지고 N,M좌표까지의 최단 경로의 칸 이동 수를 구하면 되는 문제이다. 문제를 풀기 위해 BFS(너비 우선 탐색)을 사용하였다. 문제를 풀때 배열에서의 BFS는 처음 구현해보아서 매우 힘들었다..  문제 풀이 변수static int N, M;static int[][] arr;static int[] dx = {-1, 1, 0, 0};static int[] dy = {0, 0, -1, 1};static boolean[][] visit;dx, dy ==> 상하 좌우 이동을 위해 존재visit ==> 방문 여부  public static void BFS(int x, int y) { Queue queue = new LinkedList(); queue.add(ne..

문제 이해 이 문제는 2667번 단지번호붙히기 문제와 매우 유사한 문제라는 생각을 했다.https://www.acmicpc.net/problem/2667 하지만 차이점도 존재했는데, 단지번호 붙히기 문제는 위아래,좌우 로만 이동이 가능했지만 이번 문제는 대각선 이동도 고려해줘야 했다.  문제 풀이 대각선 이동을 위해 정적 변수로 배열 dx, dy를 선언해주었다.static int[] dx={-1,0,1};static int[] dy={-1,0,1};  그리고 지도를 돌면서 dfs(깊이우선탐색)을 수행해줌으로써 연결성분을 구할 수 있다.for(int i=0; i   public static void dfs(int x, int y){ Map[x][y]=0; for(int i=0; i=0 && nx..

문제 이해 연결성분을 구하는 과정과 유사하기 때문에 dfs의 성질을 이용하여 풀어야겠다고 생각 하였다.이동은 위,아래,좌,우 만 가능하다따라서 이차원 배열에서 x좌표를 +1,-1하거나 y좌표를 +1,-1하는 방식으로 이동을 할 수 있다는 뜻이다. 문제 해결 static int[] dx = {-1, 1, 0, 0};static int[] dy = {0, 0, -1, 1}; public static void dfs(int x, int y) { arr[x][y] = 0; count += 1; for (int i = 0; i = 0 && nx = 0 && ny  arr[dx][dy]가 1 일때만 이동하여서 연결성분을 알아낼수있도록 하였고, if문에 조건을 넣어서 배열의 영역을 벗어나지 않도록 하..