# 1강 - [24 04 03, p 13497, 1강, 스프링부트 웹 개발을 열심히 하신 분들은 알고리즘을 공부하실 때 DFS, BFS 만 배우셔도 됩니다.](https://youtu.be/FXuiAHXgkN8) # 2강 - [24 04 03, p 13497, 2강, DFS(깊이 우선 탐색)은 탐색할 길이 발견되면, 그 길이 끝날 때까지 탐색합니다.](https://youtu.be/d9pU-uvAzU8) # 3강 - [24 04 03, p 13497, 3강, BFS(너비 우선 탐색)은 탐색할 길이 발견되면, 할 일 리스트(큐)에 추가(맨 끝으로 추가됨)하고 할 일 리스트에 적힌 다음 공간에 방문](https://youtu.be/NzCJqHXLdWQ) # 4강 - [24 04 03, p 13497, 4강, 타겟 넘버, 문제설명](https://youtu.be/hE3gnM6n24A) - [프로그래머스 - 코딩테스트 연습 - DFS - 레벨 2 - 자바 - 타겟 넘버](https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java) # 5강 - [24 04 03, p 13497, 5강, 타겟 넘버, 문제해설](https://youtu.be/hgR--Wif08I) ## 정답 ```java class Solution { public int solution(int[] numbers, int target) { return new NumberOfCases(numbers, target).calc(); } } class NumberOfCases { private int[] numbers; private int target; public NumberOfCases(int[] numbers, int target) { this.numbers = numbers; this.target = target; } public int calc() { return calc(0, 0); } public int calc(int depth, int sum, String history) { if ( depth == numbers.length ) return sum == target ? 1 : 0; return calc(depth + 1, sum + numbers[depth]) + calc(depth + 1, sum - numbers[depth]); } } ``` ## 정답(디버깅) ```java class Solution { public int solution(int[] numbers, int target) { return new NumberOfCases(numbers, target).calc(); } } class NumberOfCases { private int[] numbers; private int target; public NumberOfCases(int[] numbers, int target) { this.numbers = numbers; this.target = target; System.out.println("target = " + target); } public int calc() { return calc(0, 0, ""); } public int calc(int depth, int sum, String history) { if ( history.length() > 0 ) System.out.print(history + " = " + sum); if ( depth == numbers.length ) { System.out.print(sum == target ? "[성공]" : "[실패]"); } if ( history.length() > 0 ) System.out.println(); if ( depth == numbers.length ) return sum == target ? 1 : 0; return calc(depth + 1, sum + numbers[depth], history + " + " + numbers[depth]) + calc(depth + 1, sum - numbers[depth], history + " - " + numbers[depth]); } } ``` # 6강 - [24 04 03, p 13497, 6강, 타겟 넘버, 문제설명](https://youtu.be/cvXvb_iJmVM) - [프로그래머스 - 코딩테스트 연습 - BFS - 레벨 2 - 자바 - 게임 맵 최단거리](https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java) # 7강 - [24 04 03, p 13497, 7강, 타겟 넘버를 BFS 로 풀어야 하는 이유](https://youtu.be/k8DWMzxr9Tk) # 8강 - [24 04 03, p 13497, 8강, BFS 로 찾은 목적지는 기준점에서 최단거리임을 보장한다.](https://youtu.be/vE5W5CLlkJA) # 9강 - [24 04 03, p 13497, 9강, 타겟 넘버, 문제해설, 1단계, 테스트를 위한 기반 마련](https://youtu.be/tL3NCLucruc) ## 코드 ```java public class Main { public static void main(String[] args) { work1(); work2(); } private static void work1() { int correctRs = 11; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 1} } ); System.out.println("== work1 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } private static void work2() { int correctRs = -1; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 1} } ); System.out.println("== work2 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } } class Solution { public int solution(int[][] maps) { int answer = 0; return answer; } } ``` # 10강 - [24 04 03, p 13497, 10강, 타겟 넘버, 문제해설, 2단계, 큐 도입하여 최초에 0, 0의 위치를 탐색해야 한다고 설정](https://youtu.be/svnWH6JPENI) ## 코드 ```java import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { work1(); work2(); } private static void work1() { int correctRs = 11; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 1} } ); System.out.println("== work1 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } private static void work2() { int correctRs = -1; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 1} } ); System.out.println("== work2 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } } class Solution { public int solution(int[][] maps) { return new Calculator(maps).calc(); } } class Calculator { private final Queue queue; private final int[][] map; private final int n; private final int m; public Calculator(int[][] map) { this.map = map; this.n = map[0].length; this.m = map.length; this.queue = new LinkedList<>(); this.queue.add(new Point(0, 0)); } public int calc() { while (!queue.isEmpty()) { Point point = queue.poll(); int x = point.x; int y = point.y; System.out.printf("탐색(x: %d, y: %d)\n", x, y); // 이후 로직 구현 } // 실패했다면 -1 반환 return -1; } } class Point { public final int x; public final int y; public Point(int x, int y) { this.x = x; this.y = y; } } ``` # 11강 - [24 04 03, p 13497, 11강, 타겟 넘버, 문제해설, 3단계, socres 도입, socres[0][0] = 1; 처리, socres 에는 방문여부와 거리가 담길 예정](https://youtu.be/hIER4GO9rqQ) ## 코드 ```java package com.ll; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { work1(); work2(); } private static void work1() { int correctRs = 11; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 1} } ); System.out.println("== work1 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } private static void work2() { int correctRs = -1; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 1} } ); System.out.println("== work2 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } } class Solution { public int solution(int[][] maps) { return new Calculator(maps).calc(); } } class Calculator { private final Queue queue; private final int[][] map; private final int[][] scores; private final int n; private final int m; public Calculator(int[][] map) { this.map = map; this.n = map[0].length; this.m = map.length; this.scores = new int[m][n]; this.queue = new LinkedList<>(); this.queue.add(new Point(0, 0)); this.scores[0][0] = 1; } public int calc() { while (!queue.isEmpty()) { Point point = queue.poll(); System.out.printf("탐색(x: %d, y: %d)\n", point.x, point.y); if (isEndPoint(point)) { return scores[point.y][point.x]; } // 좌로 갈 수 있는지 // 우로 갈 수 있는지 // 위로 갈 수 있는지 // 아래로 갈 수 있는지 } // 실패했다면 -1 반환 return -1; } private boolean isEndPoint(Point point) { return point.x == n - 1 && point.y == m - 1; } } class Point { public final int x; public final int y; public Point(int x, int y) { this.x = x; this.y = y; } } ``` # 12강 - [24 04 04, p 13497, 12강, 타겟 넘버, 문제해설, 4단계, 각 위치마다 상하좌우를 탐색하는 행위를 반복하여 목적지에 도달](https://youtu.be/-YDDxqbd5K8) ## 코드 ```java package com.ll; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { work1(); work2(); } private static void work1() { int correctRs = 11; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 1} } ); System.out.println("== work1 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } private static void work2() { int correctRs = -1; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 1} } ); System.out.println("== work2 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } } class Solution { public int solution(int[][] maps) { return new Calculator(maps).calc(); } } class Calculator { private final Queue queue; private final int[][] map; private final int[][] scores; private final int n; private final int m; public Calculator(int[][] map) { this.map = map; this.n = map[0].length; this.m = map.length; this.scores = new int[m][n]; this.queue = new LinkedList<>(); this.queue.add(new Point(0, 0)); this.scores[0][0] = 1; } public int calc() { while (!queue.isEmpty()) { Point point = queue.poll(); System.out.printf("탐색(x: %d, y: %d)\n", point.x, point.y); if (isEndPoint(point)) { return scores[point.y][point.x]; } // 좌로 갈 수 있는지 if (canMoveLeft(point)) { queue.add(point.leftOne()); this.scores[point.y][point.x - 1] = this.scores[point.y][point.x] + 1; } // 우로 갈 수 있는지 if (canMoveRight(point)) { queue.add(point.rightOne()); this.scores[point.y][point.x + 1] = this.scores[point.y][point.x] + 1; } // 위로 갈 수 있는지 if (canMoveUp(point)) { queue.add(point.upOne()); this.scores[point.y - 1][point.x] = this.scores[point.y][point.x] + 1; } // 아래로 갈 수 있는지 if (canMoveDown(point)) { queue.add(point.downOne()); this.scores[point.y + 1][point.x] = this.scores[point.y][point.x] + 1; } } // 실패했다면 -1 반환 return -1; } private boolean canMoveLeft(Point point) { if (point.x - 1 < 0) return false; if (map[point.y][point.x - 1] == 0) return false; if (scores[point.y][point.x - 1] > 0) return false; return true; } private boolean canMoveRight(Point point) { if (point.x + 1 >= n) return false; if (map[point.y][point.x + 1] == 0) return false; if (scores[point.y][point.x + 1] > 0) return false; return true; } private boolean canMoveUp(Point point) { if (point.y - 1 < 0) return false; if (map[point.y - 1][point.x] == 0) return false; if (scores[point.y - 1][point.x] > 0) return false; return true; } private boolean canMoveDown(Point point) { if (point.y + 1 >= m) return false; if (map[point.y + 1][point.x] == 0) return false; if (scores[point.y + 1][point.x] > 0) return false; return true; } private boolean isEndPoint(Point point) { return point.x == n - 1 && point.y == m - 1; } } class Point { public final int x; public final int y; public Point(int x, int y) { this.x = x; this.y = y; } public Point leftOne() { return new Point(x - 1, y); } public Point rightOne() { return new Point(x + 1, y); } public Point upOne() { return new Point(x, y - 1); } public Point downOne() { return new Point(x, y + 1); } } ``` # 13강 - [24 04 04, p 13497, 13강, 타겟 넘버, 문제해설, 5단계, 코드를 조금 더 구조적으로 변경](https://youtu.be/C9U_bArA20c) ## 코드 ```java package com.ll; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { work1(); work2(); } private static void work1() { int correctRs = 11; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 0, 0, 1} } ); System.out.println("== work1 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } private static void work2() { int correctRs = -1; // [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] int rs = new Solution().solution( new int[][]{ {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 0, 0, 1} } ); System.out.println("== work2 =="); System.out.println("correctRs: " + correctRs); System.out.println("rs: " + rs); System.out.println(correctRs == rs ? "pass" : "fail"); } } class Solution { public int solution(int[][] maps) { return new Calculator(maps).calc(); } } class Calculator { private final Queue queue; private final int[][] map; private final int[][] scores; private final int n; private final int m; public Calculator(int[][] map) { this.map = map; this.n = map[0].length; this.m = map.length; this.scores = new int[m][n]; this.queue = new LinkedList<>(); Point basePoint = new Point(0, 0); addQueue(basePoint, basePoint); } public int calc() { while (!queue.isEmpty()) { Point point = queue.poll(); System.out.printf("탐색(x: %d, y: %d)\n", point.x, point.y); if (isEndPoint(point)) { return scores[point.y][point.x]; } // 좌로 갈 수 있는지 if (canMoveLeft(point)) { addQueue(point.leftOne(), point); } // 우로 갈 수 있는지 if (canMoveRight(point)) { addQueue(point.rightOne(), point); } // 위로 갈 수 있는지 if (canMoveUp(point)) { addQueue(point.upOne(), point); } // 아래로 갈 수 있는지 if (canMoveDown(point)) { addQueue(point.downOne(), point); } } // 실패했다면 -1 반환 return -1; } private void addQueue(Point newPoint, Point fromPoint) { queue.add(newPoint); this.scores[newPoint.y][newPoint.x] = this.scores[fromPoint.y][fromPoint.x] + 1; } private boolean canMoveLeft(Point point) { if (point.x - 1 < 0) return false; if (map[point.y][point.x - 1] == 0) return false; if (scores[point.y][point.x - 1] > 0) return false; return true; } private boolean canMoveRight(Point point) { if (point.x + 1 >= n) return false; if (map[point.y][point.x + 1] == 0) return false; if (scores[point.y][point.x + 1] > 0) return false; return true; } private boolean canMoveUp(Point point) { if (point.y - 1 < 0) return false; if (map[point.y - 1][point.x] == 0) return false; if (scores[point.y - 1][point.x] > 0) return false; return true; } private boolean canMoveDown(Point point) { if (point.y + 1 >= m) return false; if (map[point.y + 1][point.x] == 0) return false; if (scores[point.y + 1][point.x] > 0) return false; return true; } private boolean isEndPoint(Point point) { return point.x == n - 1 && point.y == m - 1; } } class Point { public final int x; public final int y; public Point(int x, int y) { this.x = x; this.y = y; } public Point leftOne() { return new Point(x - 1, y); } public Point rightOne() { return new Point(x + 1, y); } public Point upOne() { return new Point(x, y - 1); } public Point downOne() { return new Point(x, y + 1); } } ``` # 14강 - [24 04 04, p 13497, 14강, 네트워크, 문제설명](https://youtu.be/rBqo8Qt332k) - [프로그래머스 - 코딩테스트 연습 - DFS - 레벨 3 - 자바 - 네트워크](https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=java) # 15강 - [24 04 04, p 13497, 15강, 네트워크, 힌트](https://youtu.be/8ZtWkQ38PQk) # 16강 - [24 04 04, p 13497, 16강, 네트워크, 문제해설, 1단계, 테스트를 위한 기반 마련](https://youtu.be/pD6o2AEZsjs) ## 코드 ```java package com.ll; public class Main { public static void main(String[] args) { work1(); work2(); } private static void work1() { int correctRs = 2; int rs = new Solution().solution(3, new int[][]{ {1, 1, 0}, {1, 1, 0}, {0, 0, 1}, }); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } private static void work2() { int correctRs = 1; int rs = new Solution().solution(3, new int[][]{ {1, 1, 0}, {1, 1, 1}, {0, 1, 1}, }); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } } class Solution { public int solution(int n, int[][] computers) { return new Calculator(n, computers).calc(); } } class Calculator { private final int n; private final int[][] computersNetworkMatrix; public Calculator(int n, int[][] computersNetworkMatrix) { this.n = n; this.computersNetworkMatrix = computersNetworkMatrix; } public int calc() { return 0; } } ``` # 17강 - [24 04 04, p 13497, 17강, 네트워크, 문제해설, 2단계, DFS로 해결](https://youtu.be/ceUezfWj6dY) ## 코드 ```java package com.ll; public class Main { public static void main(String[] args) { work1(); work2(); } private static void work1() { int correctRs = 2; int rs = new Solution().solution(3, new int[][]{ {1, 1, 0}, {1, 1, 0}, {0, 0, 1}, }); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } private static void work2() { int correctRs = 1; int rs = new Solution().solution(3, new int[][]{ {1, 1, 0}, {1, 1, 1}, {0, 1, 1}, }); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } } class Solution { public int solution(int n, int[][] computers) { return new Calculator(n, computers).calc(); } } class Calculator { private final int n; private final int[][] computersNetworkMatrix; private final boolean[] visited; public Calculator(int n, int[][] computersNetworkMatrix) { this.n = n; this.computersNetworkMatrix = computersNetworkMatrix; visited = new boolean[n]; } public int calc() { int networkCount = 0; for (int computer = 0; computer < n; computer++) { if (visited[computer]) continue; exploreNetwork(computer); networkCount++; } return networkCount; } private void exploreNetwork(int computer) { visited[computer] = true; for (int otherComputer = 0; otherComputer < n; otherComputer++) { if (visited[otherComputer]) continue; if (computersNetworkMatrix[computer][otherComputer] == 1) exploreNetwork(otherComputer); } } } ``` # 18강 - [24 04 04, p 13497, 18강, 단어 변환, 문제설명](https://youtu.be/gMTb7a7mgEc) - [프로그래머스 - 코딩테스트 연습 - BFS - 레벨 3 - 자바 - 단어 변환](https://school.programmers.co.kr/learn/courses/30/lessons/431639?language=java) # 19강 - [24 04 04, p 13497, 19강, 단어 변환, 문제해설, 1단계, 테스트를 위한 기반 마련](https://youtu.be/YcB8JE8zjr0) ## 코드 ```java package com.ll; public class Main { public static void main(String[] args) { work1(); work2(); } // "hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4 private static void work1() { int correctRs = 4; int rs = new Solution().solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"}); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // "hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0 private static void work2() { int correctRs = 0; int rs = new Solution().solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"}); System.out.println("== work2 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } } class Solution { public int solution(String begin, String target, String[] words) { return new Calculator(begin, target, words).calc(); } } class Calculator { private final String begin; private final String target; private final String[] words; public Calculator(String begin, String target, String[] words) { this.begin = begin; this.target = target; this.words = words; } public int calc() { return 0; } } ``` # 20강 - [24 04 04, p 13497, 20강, 단어 변환, 문제해설, 2단계, 일단 변환이 가능한지만 체크](https://youtu.be/9_z3PeswXzc) ## 코드 ```java package com.ll; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { work1(); work2(); } // "hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4 private static void work1() { int correctRs = 4; int rs = new Solution().solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"}); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // "hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0 private static void work2() { int correctRs = 0; int rs = new Solution().solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"}); System.out.println("== work2 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } } class Solution { public int solution(String begin, String target, String[] words) { return new Calculator(begin, target, words).calc(); } } class Calculator { private final String target; private final String[] words; private final Queue queue; private final boolean[] visited; public Calculator(String begin, String target, String[] words) { this.target = target; this.words = words; this.visited = new boolean[words.length]; this.queue = new LinkedList<>(); queue.add(begin); } public int calc() { while (!queue.isEmpty()) { String word = queue.poll(); if (word.equals(target)) { return 1; // 찾았다 } for (int i = 0; i < words.length; i++) { String _word = words[i]; if (visited[i]) continue; if (isConvertable(word, _word)) { visited[i] = true; queue.add(_word); } } } return 0; } private boolean isConvertable(String word1, String word2) { int sameCount = 0; for (int i = 0; i < word1.length(); i++) { sameCount += word1.charAt(i) == word2.charAt(i) ? 1 : 0; } return sameCount + 1 == word1.length(); } } ``` # 21강 - [24 04 04, p 13497, 21강, 단어 변환, 문제해설, 3단계, 단어뿐 아니라 횟수까지 같이 묶어서 큐에 삽입](https://youtu.be/lJUkPnR8NWw) ## 코드 ```java import java.util.LinkedList; import java.util.Queue; class Solution { public int solution(String begin, String target, String[] words) { return new Calculator(begin, target, words).calc(); } } class Calculator { private final String target; private final String[] words; private final Queue queue; private final boolean[] visited; public Calculator(String begin, String target, String[] words) { this.target = target; this.words = words; this.visited = new boolean[words.length]; this.queue = new LinkedList<>(); queue.add(new WordTranslation(begin, 0)); } public int calc() { while (!queue.isEmpty()) { WordTranslation wt = queue.poll(); if (wt.word.equals(target)) { return wt.count; } for (int i = 0; i < words.length; i++) { String _word = words[i]; if (visited[i]) continue; if (isConvertable(wt.word, _word)) { visited[i] = true; queue.add(new WordTranslation(_word, wt.count + 1)); } } } return 0; } private boolean isConvertable(String word1, String word2) { int sameCount = 0; for (int i = 0; i < word1.length(); i++) { sameCount += word1.charAt(i) == word2.charAt(i) ? 1 : 0; } return sameCount + 1 == word1.length(); } } class WordTranslation { public final String word; public final int count; public WordTranslation(String word, int count) { this.word = word; this.count = count; } } ``` # 22강 - [24 04 04, p 13497, 22강, 아이템 줍기, 문제설명, 힌트](https://youtu.be/RFRgW_abBeU) - [프로그래머스 - 코딩테스트 연습 - BFS - 레벨 3 - 자바 - 아이템 줍기](https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=java) ## 힌트 - 아래에서 그린다는 표현은 2차원배열로 표현하라는 뜻 입니다. - 맵을 50 * 50 이 아닌 51 * 51 로 그리면 조금 더 편하다. - 맵과 도형의 가로, 너비를 2배수 증가시켜서 그려야 정확한 연산이 가능하다. # 23강 - [24 04 04, p 13497, 23강, 아이템 줍기, 문제해설, 1단계, 테스트를 위한 기반 마련](https://youtu.be/SzyWoDm5_fM) ## 코드 ```java package com.ll; public class Main { public static void main(String[] args) { work1(); work2(); work3(); work4(); work5(); } // {{1,1,7,4},{3,2,5,5},{4,3,6,9},{2,6,8,8}} 1 3 7 8 17 private static void work1() { int correctRs = 17; int rs = new Solution().solution( new int[][]{ {1, 1, 7, 4}, {3, 2, 5, 5}, {4, 3, 6, 9}, {2, 6, 8, 8} }, 1, 3, 7, 8 ); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{1,1,8,4},{2,2,4,9},{3,6,9,8},{6,3,7,7}} 9 7 6 1 11 private static void work2() { int correctRs = 11; int rs = new Solution().solution( new int[][]{ {1, 1, 8, 4}, {2, 2, 4, 9}, {3, 6, 9, 8}, {6, 3, 7, 7} }, 9, 7, 6, 1 ); System.out.println("== work2 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{1,1,5,7}} 1 1 4 7 9 private static void work3() { int correctRs = 9; int rs = new Solution().solution( new int[][]{ {1, 1, 5, 7} }, 1, 1, 4, 7 ); System.out.println("== work3 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{2,1,7,5},{6,4,10,10}} 3 1 7 10 15 private static void work4() { int correctRs = 15; int rs = new Solution().solution( new int[][]{ {2, 1, 7, 5}, {6, 4, 10, 10} }, 3, 1, 7, 10 ); System.out.println("== work4 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{2,2,5,5},{1,3,6,4},{3,1,4,6}} 1 4 6 3 10 private static void work5() { int correctRs = 10; int rs = new Solution().solution( new int[][]{ {2, 2, 5, 5}, {1, 3, 6, 4}, {3, 1, 4, 6} }, 1, 4, 6, 3 ); System.out.println("== work5 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } } class Solution { public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { return new Calculator(rectangle, characterX, characterY, itemX, itemY).calc(); } } class Calculator { private final int[][] rectangles; private final int characterX; private final int characterY; private final int itemX; private final int itemY; public Calculator(int[][] rectangles, int characterX, int characterY, int itemX, int itemY) { this.rectangles = rectangles; this.characterX = characterX; this.characterY = characterY; this.itemX = itemX; this.itemY = itemY; } public int calc() { return 0; } } ``` # 24강 - [24 04 04, p 13497, 24강, 모든 숫자에 2를 곱해서 계산, 맵을 초기화](https://youtu.be/ozDH6PgnbcI) ## 코드 ```java package com.ll; public class Main { public static void main(String[] args) { work1(); work2(); work3(); work4(); work5(); } // {{1,1,7,4},{3,2,5,5},{4,3,6,9},{2,6,8,8}} 1 3 7 8 17 private static void work1() { int correctRs = 17; int rs = new Solution().solution( new int[][]{ {1, 1, 7, 4}, {3, 2, 5, 5}, {4, 3, 6, 9}, {2, 6, 8, 8} }, 1, 3, 7, 8 ); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{1,1,8,4},{2,2,4,9},{3,6,9,8},{6,3,7,7}} 9 7 6 1 11 private static void work2() { int correctRs = 11; int rs = new Solution().solution( new int[][]{ {1, 1, 8, 4}, {2, 2, 4, 9}, {3, 6, 9, 8}, {6, 3, 7, 7} }, 9, 7, 6, 1 ); System.out.println("== work2 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{1,1,5,7}} 1 1 4 7 9 private static void work3() { int correctRs = 9; int rs = new Solution().solution( new int[][]{ {1, 1, 5, 7} }, 1, 1, 4, 7 ); System.out.println("== work3 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{2,1,7,5},{6,4,10,10}} 3 1 7 10 15 private static void work4() { int correctRs = 15; int rs = new Solution().solution( new int[][]{ {2, 1, 7, 5}, {6, 4, 10, 10} }, 3, 1, 7, 10 ); System.out.println("== work4 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{2,2,5,5},{1,3,6,4},{3,1,4,6}} 1 4 6 3 10 private static void work5() { int correctRs = 10; int rs = new Solution().solution( new int[][]{ {2, 2, 5, 5}, {1, 3, 6, 4}, {3, 1, 4, 6} }, 1, 4, 6, 3 ); System.out.println("== work5 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } } class Solution { public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { return new Calculator(rectangle, characterX, characterY, itemX, itemY).calc(); } } class Calculator { private final int n; private final int m; private final int[][] map; private final Point characterPoint; private final Point itemPoint; public Calculator(int[][] rectangles, int characterX, int characterY, int itemX, int itemY) { this.n = (50 + 1) * 2; this.m = (50 + 1) * 2; this.map = new int[m][n]; initMap(rectangles); this.characterPoint = new Point(characterX * 2, characterY * 2); this.itemPoint = new Point(itemX * 2, itemY * 2); } private void initMap(int[][] rectangles) { for (int[] rectangle : rectangles) { Point leftBottom = new Point(rectangle[0] * 2, rectangle[1] * 2); Point rightTop = new Point(rectangle[2] * 2, rectangle[3] * 2); fillBlockOnContent(leftBottom, rightTop); fillPathOnOutline(leftBottom, rightTop); } } private void fillBlockOnContent(Point leftBottom, Point rightTop) { for (int y = leftBottom.y + 1; y < rightTop.y; y++) { for (int x = leftBottom.x + 1; x < rightTop.x; x++) { map[y][x] = 1; } } } private void fillPathOnOutline(Point leftBottom, Point rightTop) { for (int y = leftBottom.y; y <= rightTop.y; y++) { map[y][leftBottom.x] = map[y][leftBottom.x] == 1 ? 1 : 2; map[y][rightTop.x] = map[y][rightTop.x] == 1 ? 1 : 2; } for (int x = leftBottom.x; x <= rightTop.x; x++) { map[leftBottom.y][x] = map[leftBottom.y][x] == 1 ? 1 : 2; map[rightTop.y][x] = map[rightTop.y][x] == 1 ? 1 : 2; } } public int calc() { return 0; } } class Point { public final int x; public final int y; public Point(int x, int y) { this.x = x; this.y = y; } } ``` # 25강 - [24 04 04, p 13497, 25강, scores 를 이용해서 한번 갔던 길을 가지 않도록, 최종 결과에 2를 나눠서 리턴](https://youtu.be/g2RUole32Vw) ## 코드 ```java package com.ll; import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { work1(); work2(); work3(); work4(); work5(); } // {{1,1,7,4},{3,2,5,5},{4,3,6,9},{2,6,8,8}} 1 3 7 8 17 private static void work1() { int correctRs = 17; int rs = new Solution().solution( new int[][]{ {1, 1, 7, 4}, {3, 2, 5, 5}, {4, 3, 6, 9}, {2, 6, 8, 8} }, 1, 3, 7, 8 ); System.out.println("== work1 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{1,1,8,4},{2,2,4,9},{3,6,9,8},{6,3,7,7}} 9 7 6 1 11 private static void work2() { int correctRs = 11; int rs = new Solution().solution( new int[][]{ {1, 1, 8, 4}, {2, 2, 4, 9}, {3, 6, 9, 8}, {6, 3, 7, 7} }, 9, 7, 6, 1 ); System.out.println("== work2 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{1,1,5,7}} 1 1 4 7 9 private static void work3() { int correctRs = 9; int rs = new Solution().solution( new int[][]{ {1, 1, 5, 7} }, 1, 1, 4, 7 ); System.out.println("== work3 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{2,1,7,5},{6,4,10,10}} 3 1 7 10 15 private static void work4() { int correctRs = 15; int rs = new Solution().solution( new int[][]{ {2, 1, 7, 5}, {6, 4, 10, 10} }, 3, 1, 7, 10 ); System.out.println("== work4 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } // {{2,2,5,5},{1,3,6,4},{3,1,4,6}} 1 4 6 3 10 private static void work5() { int correctRs = 10; int rs = new Solution().solution( new int[][]{ {2, 2, 5, 5}, {1, 3, 6, 4}, {3, 1, 4, 6} }, 1, 4, 6, 3 ); System.out.println("== work5 =="); System.out.println("correctRs : " + correctRs); System.out.println("rs : " + rs); } } class Solution { public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { return new Calculator(rectangle, characterX, characterY, itemX, itemY).calc(); } } class Calculator { private final int n; private final int m; private final int[][] map; private final int[][] scores; private final Queue queue; private final Point characterPoint; private final Point itemPoint; public Calculator(int[][] rectangles, int characterX, int characterY, int itemX, int itemY) { this.n = (50 + 1) * 2; this.m = (50 + 1) * 2; this.map = new int[m][n]; this.scores = new int[m][n]; this.queue = new LinkedList<>(); initMap(rectangles); this.characterPoint = new Point(characterX * 2, characterY * 2); this.itemPoint = new Point(itemX * 2, itemY * 2); addQueue(characterPoint, null); } private void addQueue(Point newPoint, Point fromPoint) { queue.add(newPoint); if (fromPoint != null) { scores[newPoint.y][newPoint.x] = scores[fromPoint.y][fromPoint.x] + 1; } } private void initMap(int[][] rectangles) { for (int[] rectangle : rectangles) { Point leftBottom = new Point(rectangle[0] * 2, rectangle[1] * 2); Point rightTop = new Point(rectangle[2] * 2, rectangle[3] * 2); fillBlockOnContent(leftBottom, rightTop); fillPathOnOutline(leftBottom, rightTop); } } private void fillBlockOnContent(Point leftBottom, Point rightTop) { for (int y = leftBottom.y + 1; y < rightTop.y; y++) { for (int x = leftBottom.x + 1; x < rightTop.x; x++) { map[y][x] = 1; } } } private void fillPathOnOutline(Point leftBottom, Point rightTop) { for (int y = leftBottom.y; y <= rightTop.y; y++) { map[y][leftBottom.x] = map[y][leftBottom.x] == 1 ? 1 : 2; map[y][rightTop.x] = map[y][rightTop.x] == 1 ? 1 : 2; } for (int x = leftBottom.x; x <= rightTop.x; x++) { map[leftBottom.y][x] = map[leftBottom.y][x] == 1 ? 1 : 2; map[rightTop.y][x] = map[rightTop.y][x] == 1 ? 1 : 2; } } public int calc() { while (!queue.isEmpty()) { Point point = queue.poll(); if (isEndPoint(point)) return scores[point.y][point.x] / 2; if (canMoveLeft(point)) addQueue(point.leftOne(), point); if (canMoveRight(point)) addQueue(point.rightOne(), point); if (canMoveUp(point)) addQueue(point.upOne(), point); if (canMoveDown(point)) addQueue(point.downOne(), point); } throw new IllegalStateException(); } private boolean canMoveLeft(Point point) { if (scores[point.y][point.x - 1] > 0) return false; return map[point.y][point.x - 1] == 2; } private boolean canMoveRight(Point point) { if (scores[point.y][point.x + 1] > 0) return false; return map[point.y][point.x + 1] == 2; } private boolean canMoveUp(Point point) { if (scores[point.y + 1][point.x] > 0) return false; return map[point.y + 1][point.x] == 2; } private boolean canMoveDown(Point point) { if (scores[point.y - 1][point.x] > 0) return false; return map[point.y - 1][point.x] == 2; } private boolean isEndPoint(Point point) { return point.x == itemPoint.x && point.y == itemPoint.y; } } class Point { public final int x; public final int y; public Point(int x, int y) { this.x = x; this.y = y; } public Point leftOne() { return new Point(x - 1, y); } public Point rightOne() { return new Point(x + 1, y); } public Point upOne() { return new Point(x, y + 1); } public Point downOne() { return new Point(x, y - 1); } } ``` # 26강 - [24 04 04, p 13497, 26강, 퍼즐 조각 채우기, 문제설명, 힌트](https://youtu.be/KupjLGBaiV4) - [프로그래머스 - 코딩테스트 연습 - BFS - 레벨 3 - 자바 - 퍼즐 조각 채우기](https://school.programmers.co.kr/learn/courses/30/lessons/84021?language=java)