연향동큰손

문제 이해 기존의 BFS 문제들이랑 크게 다를것은 없었다. 이동 경로만 잘 생각해주면 그렇게 어려운 문제는 아니다. 이동 경로 1) 1칸 앞으로 이동2) 1칸 뒤로 이동3) 현 위치 * 2 만큼 이동 이러한 이동을 구현하기 위해 move 배열 생성static int[] move = {1,-1,2}; 이동 규칙1) 방문했던 곳을 방문X2) 이동에 걸리는 시간을 출력해야 하므로 이동 할때마다 시간 +13) 방문했다면 visit 배열에 방문을 표시 문제 풀이 public static void BFS(int now){ Queue queue = new LinkedList(); queue.add(now); visit[now]=true; while(!queue.isEmpty()){ ..

문제 이해 그래프 문제들은 기본적인 틀을 벗어나지 않는 것 같다.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문에 조건을 넣어서 배열의 영역을 벗어나지 않도록 하..

문제 이해 그래프에서 DFS(깊이 우선 탐색) 와 BFS(너비 우선 탐색) 을 구현하면 되는 문제이다. 그래프를 구현하는 방법에는 인접행렬과 연결리스트로 표현하는 것이 있는데 이번 문제에서는 연결리스트로 구현해 보았다. 문제 풀이 1) ArrayList만들어주기ArrayList> graph = new ArrayList(); 2) 각 노드 별 리스트를 만들어준다.for(int i=0; i());} 3) 각 노드들의 연결 정보를 입력 받는다.for(int i=0; ipublic static void putEdge(ArrayList> graph, int x, int y){ graph.get(x).add(y); graph.get(y).add(x);}  4) *** 각 노드에 있는 연결 리스트를 정렬해..

문제 이해 주어진 수열의 부분수열의 합이 S가 되는 경우의 수를 구해주면 되는 문제이다.모든 경우의 수를 집고 넘어가야 하므로 dfs를 이용하면 쉽게 풀 수 있다. 문제 풀이 private static void dfs(int start, int sum){ if(start==N) { if (sum == S) { count++; } return; } dfs(start+1,sum+num[start]); dfs(start+1,sum);}  배열에서 선택된 수를 더할지 아니면 그냥 넘어갈지를 결정하기 위해서 재귀 호출을 이용하였다. 그리고 start변수가 N이 되면 배열의 끝까지 도달한 경우인데 이때의 sum이 S와 같으면 경우의 수에..

문제 접근 문제를 보자마자 HashSet의 특징이 떠올라서 HashSet을 이용하여 풀면 간단하게 풀 수 있겠다는 생각을 가지고 구현해보았다. import java.util.HashSet;import java.util.Scanner;public class Problem11723 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); String calculation; int num; HashSet S = new HashSet(); for(int i=0; i  제출결과 시간초과가 발생..

문제 이해 부등호로 이루어진 문자열이 주어지면 부등호 사이에 올수있는 모든 숫자열 중 최솟값과 최대값을 구해주면 된다.모든 경우를 구해줘야 하므로 dfs를 이용하면 쉽게 구할 수 있다. 문제 풀이 맨 앞의 숫자가 0~9까지 중 올수있는 모든 경우의 수를 구해줘야 하므로 for문을 이용하여 dfs를 호출해준다.for (int i = 0; i   ※매개변수start ==>가장 최근에 삽입된 숫자(dfs에서는 start뒤에 들어올 숫자를 결정)count ==> 삽입된 숫자의 갯수num ==> 부등호 사이에 들어가는 숫자들을 표현한 문자열static void dfs(int start, int count, String num) { if (count == N) { number.add(num); /..

문제 접근 두 팀의 능력치의 최소 차이를 구하면 된다. 인원의 절반은 스타트 팀, 나머지는 링크 팀으로 배치시키는 모든 경우의 수를 구해야 하므로 dfs를 수행해주면 된다. dfs의 종료 조건 :  전체 인원의 절반이 스타트 팀으로 빠졌다면 그 상황에서의 능력치의 차이를 구해주면 된다.   문제 풀이 N = 인원수S = 개인 능력치를 저장하는 이차원 배열visit = dfs에서 방문 유무를 확인할때 쓰이는 일차원 배열Min = 최소 능력치 차이를 저장static int N;static int[][] S;static boolean[] visit;static int Min = Integer.MAX_VALUE;  idx = 현재 선택된 사원count =  스타트 팀으로 들어간 인원 수 (절반이 스타트 팀에 들..