Skip to content

Commit d2bcdb8

Browse files
GoogleokGoogleok
committed
29주차 알고리즘 완료
1 parent 41f9cee commit d2bcdb8

3 files changed

Lines changed: 169 additions & 0 deletions

File tree

‎src/programmers/level2/week_29/Solution001.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package programmers.level2.week_29;
2+
3+
/**
4+
* 예상 대진표
5+
* https://programmers.co.kr/learn/courses/30/lessons/12985?language=java
6+
*/
7+
public class Solution001 {
8+
9+
public static void main(String[] args) {
10+
Solution001 sol = new Solution001();
11+
System.out.println(sol.solution(8, 4, 5));
12+
}
13+
14+
public int solution(int n, int a, int b) {
15+
int answer = 0;
16+
17+
while (a != b) {
18+
a = (a / 2) + (a % 2);
19+
b = (b / 2) + (b % 2);
20+
answer++;
21+
}
22+
23+
return answer;
24+
}
25+
}

‎src/programmers/level2/week_29/Solution002.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package programmers.level2.week_29;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* 단체사진 찍기 > 다른 풀이 참조함
8+
* https://programmers.co.kr/learn/courses/30/lessons/1835?language=java
9+
*/
10+
public class Solution002 {
11+
static String[] d;
12+
static Map<Character, Integer> map;
13+
static boolean[] visited;
14+
static int[] position;
15+
static int answer;
16+
17+
public static void main(String[] args) {
18+
int n = 2;
19+
String[] data = {"N~F=0", "R~T>2"};
20+
Solution002 sol = new Solution002();
21+
System.out.println(sol.solution(n, data));
22+
}
23+
24+
public int solution(int n, String[] data) {
25+
d = data;
26+
map = new HashMap<>();
27+
visited = new boolean[8];
28+
position = new int[8];
29+
answer = 0;
30+
map.put('A', 0);
31+
map.put('C', 1);
32+
map.put('F', 2);
33+
map.put('J', 3);
34+
map.put('M', 4);
35+
map.put('N', 5);
36+
map.put('R', 6);
37+
map.put('T', 7);
38+
dfs(0);
39+
return answer;
40+
}
41+
42+
public void dfs(int idx) {
43+
if (idx == 8) {
44+
if (check()) answer++;
45+
} else {
46+
for (int i = 0; i < 8; i++) {
47+
if (!visited[i]) {
48+
visited[i] = true;
49+
position[idx] = i;
50+
dfs(idx + 1);
51+
visited[i] = false;
52+
}
53+
}
54+
}
55+
}
56+
57+
public boolean check() {
58+
int a, b, res;
59+
char op;
60+
for (String s : d) {
61+
a = position[map.get(s.charAt(0))];
62+
b = position[map.get(s.charAt(2))];
63+
op = s.charAt(3);
64+
res = s.charAt(4) - '0' + 1;
65+
66+
if (op == '=') {
67+
if (Math.abs(a - b) != res) return false;
68+
} else if (op == '>') {
69+
if (Math.abs(a - b) <= res) return false;
70+
} else {
71+
if (Math.abs(a - b) >= res) return false;
72+
}
73+
}
74+
75+
return true;
76+
}
77+
78+
}

‎src/programmers/level2/week_29/Solution003.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package programmers.level2.week_29;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* 게임 맵 최단거리
8+
* https://programmers.co.kr/learn/courses/30/lessons/1844?language=java
9+
*/
10+
public class Solution003 {
11+
12+
int[] dx = {0, 1, 0, -1};
13+
int[] dy = {-1, 0, 1, 0};
14+
boolean[][] visited;
15+
int n, m;
16+
17+
public static void main(String[] args) {
18+
Solution003 sol = new Solution003();
19+
int[][] maps = {{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}};
20+
System.out.println(sol.solution(maps));
21+
}
22+
23+
public int solution(int[][] maps) {
24+
n = maps.length;
25+
m = maps[0].length;
26+
27+
visited = new boolean[n][m];
28+
return bfs(0, 0, maps);
29+
}
30+
31+
public int bfs(int x, int y, int[][] maps) {
32+
Queue<Node> q = new LinkedList<>();
33+
q.offer(new Node(x, y, 1));
34+
visited[x][y] = true;
35+
36+
while (!q.isEmpty()) {
37+
Node node = q.poll();
38+
if (node.x == n - 1 && node.y == m - 1) return node.cost;
39+
40+
for (int i = 0; i < 4; i++) {
41+
int nx = node.x + dx[i];
42+
int ny = node.y + dy[i];
43+
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
44+
if (maps[nx][ny] == 1 && !visited[nx][ny]) {
45+
visited[nx][ny] = true;
46+
q.offer(new Node(nx, ny, node.cost + 1));
47+
}
48+
}
49+
}
50+
}
51+
return -1;
52+
}
53+
54+
55+
public static class Node {
56+
int x;
57+
int y;
58+
int cost;
59+
60+
public Node(int x, int y, int cost) {
61+
this.x = x;
62+
this.y = y;
63+
this.cost = cost;
64+
}
65+
}
66+
}

0 commit comments

Comments
 (0)