IT LAB

난이도 : Level 3 문제링크 문자열 begin, target과 문자열 배열 words가 주어진다 주어진 변환과정을 사용하여 begin에서 target으로 변환하는 최소한의 단계수를 리턴하라 변환 제약사항 한 번에 한 개의 알파벳만 바꿀 수 있음 words에 있는 단어로만 변환할 수 있음 example "hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] "hit" -> "hot" -> "dot" -> "dog" -> "cog" => 4 해설 BFS 탐색을 하여 모든 경우의 수를 찾는다. 큐 자료구조를 사용하므로, 너비 탐색중에 target이 만들어지는 가장 최근의 변환횟수가 가장 최소의 변환횟수이다. 큐에 들어갈 단어가 유효성 검사를 통과해야 큐에 들어갈..

난이도 : Level 3 문제링크 컴퓨터 갯수와 각 컴퓨터의 연결 정보에 대한 2차원 정수형 배열이 주어진다 컴퓨터의 연결 정보에 대한 배열 i번 컴퓨터와 j번 컴퓨터의 연결상태를 나타냄 computers[i][j] == 1 네트워크 갯수를 구하라 해설 네트워크 전체를 탐색하기 위해 dfs 탐색을 시도합니다. (연결된 네트워크의 모든 노드들을 방문할 수 있습니다) dfs 탐색 대상 컴퓨터 연결된 또 다른 컴퓨터가 존재함 (네트워크 탐색을 통해) 방문하지 않은 컴퓨터 혼자 있는 컴퓨터도 네트워크 이므로 네트워크 수에 더해줍니다 (네트워크 탐색 시에) 방문하지 않은 컴퓨터 입니다. class Solution { boolean[] visited; public int solution(int n, int[][] ..

난이도 : Level 2 문제링크 캐릭터가 상대 팀 진영까지 도착하기 위해 지나가야 하는 칸의 최소갯수를 리턴하라 캐릭터는 맨 좌측 상단에 위치한다 상대방 진영은 맨 우측 하단에 위치한다 게임 맵에서 벽은 지나갈 수 없다 해설 최소 비용 경로를 구해야 하기 때문에 BFS 탐색 알고리즘을 사용하여 푼다. 방문한 좌표들을 큐로 넣고 큐가 비어있지 않을 때까지 반복한다. 방문한 좌표에 지나온 칸 수를 같이 저장하고, 목표지에 도착시 그동안 저장했던 칸 수를 리턴한다. import java.util.*; class Solution { int[] dy, dx; boolean[][] visited; public int solution(int[][] maps) { int r_ = maps.length-1, c_ = ..

난이도 : Level 2 문제링크 n개의 음이 아닌 정수형 배열이 주어진다 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 리턴하라 해설 깊이 탐색으로 모든 경우를 조사한다. numbers의 길이만큼의 뎁스로 탐색했을 때의 합이 target과 같은지 확인한다. 현재 뎁스에서 탐색하려는 숫자의 인덱스는 numbers의 인덱스와 같다. 첫번째 수부터 부호를 바꿀 수 있으므로 호출시의 뎁스를 -1로 전달한다 class Solution { public int solution(int[] numbers, int target) { return dfs(-1, numbers, target, 0); } private int dfs(int depth, int[] numbers, int target, int..