알고리즘 검색 결과

해당 글 181건

[백준 4991] 로봇청소기 -JAVA // le_effort//

까다로운 문제였다. 사용하는 알고리즘 = bfs , dfs를 이용한 순열 방문했던 칸을 계속 방문 할 수 있다는 것은 일반적인 bfs를 하는게 아니라 전체 거리를 구해줘야함 전체거리란 2번 설명에 있음 전체적인 흐름은 1. 방문할 수 없는 더러운 칸이 존재하는가? 존재하면 -1 출력하고 끝 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 public static boolean isPossible(int x, int y) { int copy_map [][] = new int[h][w]; for(int i=0; iColored by Color Scripter 1 2 3 4 5 6 7 8 9 ..
알고리즘 2020. 3. 5. 14:45

[백준 9328] 열쇠 -JAVA //le_effort//

여러가지 아이디어가 필요한 문제였다 핵심 아이디어는 열쇠와 벽을 처리 해주는 것 인데 대문자로 이루어진 문은 소문자로 이루어진 열쇠가 있어야 지나 갈 수 있다 하지만 이런 경우 에는 어떻게 할 까? ...... .A..a *$*** 이 경우 일반적인 bfs 탐색을 0,0 부터 진행 할 시 A가 a보다 먼저 탐색이 진행된다 하지만 a 열쇠가 접근 할 수 있는 곳에 있으니 저 A문을 열 수 있어야 한다. 이는 열쇠가 없어서 못여는 문이 있을경우 일단 리스트에 넣어놓는 것 이다. 나는 열쇠와 문을 아스키 코드로 처리를 했는데 알파벳은 대소문자를 떠나서 A~Z 총 25개가 있다. int tmp = 'A'-'A' =0; int tmp = 'B'-'A" =1; int tmp = 'C'-'A' =2; 즉 비교대상 -..
알고리즘 2020. 3. 4. 16:32

[백준 9376] 탈옥 -JAVA // le_effort//

여지껏 푼 bfs 문제중에 제일 어려웠던것 같다... 맨 처음 틀린 접근 방법: 문의 개수를 카운트 하고 dfs에서 문의 개수에 도달하면 하는 방법으로 했었는데 맵이 100,100 으로 커지면 정말 말도 안되는 연산시간을 요구하기 때문에 하면 안됨으로 실패했다 dfs할 땐 문이 8개면 if(level == 8) return 하는 식으로 접근 했었고 map[x][y]='.' (문에서 빈칸으로 바꿔줌) dfs(level+1) map[x][y] = '#' dfs(level+1) // 문을 안바꿔줌 이런식으로 했었는데 틀린 접근이였다 결국 어떻게 풀어야 할 지 몰라서 다른 블로그를 참고했는데 정말 어려웠다 나는 이런식의 문제는 맵을 바꾸는 방법(문을 빈칸으로 바꾸고 안되면 빈칸으로 바꾼걸 다시 문으로 바꿈 ) ..
알고리즘 2020. 3. 4. 14:22

[백준 2589] 보물섬 - JAVA // le_effort//

일반적인 bfs와 달리 각 정점 ( 위 문제에선 L) 을 기준으로 다 bfs를 진행주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 import java.io.*; import java.util.*; public class Main { static int n,m; static int max = 0; static int dist[][]; static int dx[] = {0,0,..
알고리즘 2020. 3. 4. 12:57

[백준 12851] 숨바꼭질2 -JAVA // le_effort//

기존 숨바꼭질 문제와 다른점은 중복 방문을 부분적으로 허용해야 한다는 것이다 예를 들어서 1->2->3 을 갈 때 1, 1*2 , 1*2+1 = 3번 1, 1+1 1+1+1 = 3번 이런 식으로 +, -, * 를 다른 경우의 수로 쳐줘야 한다. 하지만 최소시간을 구하는 것 이므로 4를 간다 치면 1, 1*2 , 2*2 를 하면 3번만에 갈 수 있지만 1, 1+1 ,1+1+1 ,1+1+1+1 는 4번이 걸림으로 고려를 하지 않아줘도 된다 즉 같은 시간대 (코드에선 반복문 내에서)만 처리를 해주면 된다. if(!visited[n]) 이라면 visited[n] = true q.add(n) 이런 진행이 아니라 일단 큐에 집어넣고 큐에서 뺏을때 visited 처리를 해주면 된다 1 2 3 4 5 6 7 8 9 1..
알고리즘 2020. 3. 3. 14:32

[백준 2251] 물통 -JAVA // le_effort//

쉽게 풀릴줄 알았는데 고생한 문제다... 고려해야 하는 조건은 물통 A B C A->B A->C B->A B->C C->A C->B 이렇게 옮길수 있는 모든 경우의수를 확인해주면 되는데 한 번 방문 했던 좌표 a물의양, b물의양 , c물의양 은 굳이 할 필요가 없으니 continue를 해주면 된다 또 고려해야 할 조건이 있는데, 물을 정해진 양 만큼 부을수 있는게 아니라 부을 통에 꽉찰때까지 부으므로 예를 들어, A물통에 있는 물을 B물통으로 옮긴다고 할 때 A물통에 있는 물을 B물통에 다 부어도 B물통이 수용할수 있는가 ? (B물통의 총 용량을 넘지 않는가) 이것만 조건 분류를 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..
알고리즘 2020. 3. 3. 13:00

[백준9019] DSLR -JAVA // le_effort//

bfs로 진행 하고 한 단계에서 D S L R 을 하면서 조건을 충족하면 된다. 나는 L연산과 R연산을 할 때 하나하나 배열에다가 각 자리수에 넣어줬는데 ex) 4321 arr[0]=4 arr[1]=3 arr[2]=2 arr[3]=1; 다 풀고 다른 코드를 참고하니까 더 좋은 방법이 있었다 int r = (x%10)*1000+x/10; int l = (x%1000)*10+x/1000; 이런식으로 하면 번거롭게 안해도 되지만 생각이 나지 않아 일일히 구현했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50..
알고리즘 2020. 3. 3. 10:49

[백준 7453] 합이 0인 네 정수 -JAVA // le_effort//

문제만 오랫동안 쳐다본 거 같다. 문제를 이해하지 못했다 저기서 A B C D 배열이 어디있지? 이 생각부터 들었는데 배열이 세로로 되어있는 것이다 즉 A배열 B배열 -45 22 -41 -27 -36 53 -36 30 26 -38 -32 -54 그리고 n이 4000이니 A B C D 전부 4중반복문으로 검사를 하면 시간 내에 들어오지 못한다 그래서 두개의 배열을 한 개로 묶어서 해주는데 AB배열 ( 크기가 2일때 A [0]+B [0] A [0]+B [1] A [1]+B [0] A [1]+B [1]) CD 배열 이하 동문 그리고 주의할 점이 있는데 밑 코드 중 AB_cnt와 CD_cnt 그리고 ans는 int형을 벗어날 수 있으므로 long으로 써야 한다. 그러곤 여타 다른 문제와 같이 투 포인터 알고리즘..
알고리즘 2020. 3. 3. 10:04