SWEA

[SWEA] [모의 SW 역량테스트] 5656 - 벽돌 깨기 (자바 Java)

dfs와 bfs를 활용하여 문제를 풀었다. dfs는 벽돌 깨기를 진행하는 과정을, bfs는 특정 벽돌을 깨뜨렸을 때의 연쇄 작용을 구현하기 위해 사용했다. 벽돌 깨기의 경우 한 번 깬 벽돌의 column에 대해서도 다시 벽돌을 깰 수 있으니 방문 여부를 저장할 필요가 없다. // col에 따라 벽돌깨기 진행 for (int i = 0; i < W; i++) dfs(i, 0); dfs는 N번 진행하기 때문에 N이 되었을 때 남은 벽돌 수를 세어서 ans와 비교하였다. 그리고 세로줄 (column)에 대해 벽돌을 깨야 하니까 i열에 대해 map[r][i]가 0이 아닌 경우에 벽돌 깨기 (game)을 진행했다. static void dfs(int i, int depth) { if (depth == N) { i..

[SWEA][모의 SW 테스트] 2105 - 디저트 카페 (자바/Java)

대각선으로 사방탐색을 하는 문제다. 주의해야할 조건은 같은 숫자의 디저트를 만나면 안된다. 시작점을 제외하고 이미 방문했던 곳은 다시 방문할 수 없다. 시작점으로 돌아오도록 사각형이 그려져야 한다. 최대한 많은 디저트를 먹어야 한다. map의 좌표가 N일 때, 대각선으로 투어를 해야하기 때문에 양 끝 꼭짓점에서는 순회를 시작할 수 없다. 가장 큰 사각형의 가로 세로의 합은 N-1이다. 위 사진에서 N은 5고, 두 사각형이 가능한 최대 길이의 사각형이다. 왼쪽의 경우 가로가 3, 세로가 1이고 오른쪽은 가로가 2, 세로가 2다. 일직선이나 자기 자신만 투어하는 경우는 불가능하기 때문에 사각형의 한 변의 최소 길이는 1, 최대 길이는 N-2가 될 것이다. 이를 활용해서 두 변의 길이의 합이 최대일 때부터 최..

[SWEA] 1767 - 프로세서 연결하기 (자바/Java)

조합을 통해 경우의 수를 한정하는 방법을 자주 사용해야 할 것 같다. 처음에는 그냥 dfs로 풀어서 답은 맞았는데, 시간과 메모리를 너무 많이 잡아 먹었다. 지금 생각해보니 필요 없는 경우의 수까지 모두 탐색해서 그런 것 같다. 연결하는 코어의 수가 최대여야 하기 때문에, 모든 코어를 연결하는 경우의 수부터 dfs를 진행하고, 만약 그 수의 코어를 연결할 수 없다면 코어의 개수 N 중 N-1개, N-2개를 뽑는 조합을 통해 dfs를 반복하여 결과값이 나올 때까지 계속하면 된다. 이런 경우에서는 조합을 활용하는 게 유용한 것 같다. for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { arr[i][j] = sc.nextInt(); if (arr[i][j] ..

[SWEA] 4008 - 숫자 만들기 (자바/Java)

dfs를 통해 가능한 연산 결과를 완전 탐색하며 최대, 최소값을 저장하였다. 연산을 N-1번 수행하니까 idx가 N-1이 될 때 연산이 끝난 것이므로 함수를 return 한다. 연산자 배열에서 각 인덱스의 값이 0이 아니면 그 연산자로 계산할 수 있는 것이니까 계산 값을 재귀적으로 함수에 넣어준다. static void dfs(int idx, int res) { if (idx == N - 1) { min = Math.min(res, min); max = Math.max(res, max); return; } for (int i = 0; i < 4; i++) if (op[i] != 0) { op[i]--; dfs(idx + 1, cal(i, res, nums[idx + 1])); op[i]++; } } 가능..

[SWEA] 2819 - 격자판의 숫자 이어 붙이기

배열의 모든 원소에 대해 사방탐색을 6번 진행하는 것이다. dfs를 통해 구현하면 되는데, 한 번 방문한 원소도 다시 방문할 수 있으니 방문여부를 검사할 필요는 없다. 결과값의 중복을 제거하기 위해 hashSet을 사용하였다. 7개의 결과값을 담을 ans배열을 static으로 선언하여 depth가 1 증가할 때마다 ans[depth]에 수를 담았다. 모든 원소에 대해 dfs를 수행하고, ans배열의 0번 index에 초기값을 담아 진행한다. for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) { ans[0] = arr[i][j]; dfs(arr, i, j, 1); } dfs는 사방탐색으로 한다. 먼저 깊이가 7이 되면 결과값을 return한다. 그 다음 사..

[SWEA] 1231 - 중위 순회

트리가 완전 이진트리 형식으로 주어지기 때문에, 배열로 트리를 만들어서 구현하였다. 입력값 중 index와 해당 알파벳 말고는 사용하지 않아도 구현이 가능하다. (index도 사실 순서대로 들어오기 때문에 필요하지 않다) 배열의 index를 1부터 사용하여 i가 인덱스인 노드의 자식 노드는 각각 2*i, 2*i+1의 인덱스를 가진다. 이를 활용하면 배열을 이진트리처럼 활용하여 전위, 중위, 후위 순회가 가능하다. String[] tree = new String[N + 1]; for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int index = Integer.parseInt(st.nextToken()..

[SWEA] 1873 - 상호의 배틀 필드 (자바/Java)

shoot을 할 때 각 방향을 정의하기 위해 HashMap을 활용하였다. 각 방향을 key로 하고, 방향에 따라 달라지는 dr과 dc를 길이 2의 배열에 담아 value로 지정하였다. HashMap dir = new HashMap(); // 각 방향의 dr dc dir.put('', new Integer[] { 0, 1 }); dir.put('^', new Integer[] { -1, 0 }); dir.put('v', new Integer[] { 1, 0 }); 그리고 입력받은 문자열을 char 하나씩 문자열 배열로 만들었다. StringTokenizer st = new StringTokenizer(br.readLine()); int H = Integer.parseInt(st.nextToken()); /..

[SWEA] 1216 - 회문 2 (자바/Java)

처음에는 각 행과 열에서 0과 99에서 시작해서, 두 값이 같으면 start와 end를 1씩 감소 시키고, 아닌 경우에는 start와 end 중 하나만 감소시키며 검사하려고 하였는데, 재귀로 구현하였더니 case가 너무 많고 예외처리가 잘 안되어서 무한 루프가 일어났다. 두 값이 같지 않을 경우 start를 1 증가시키거나, end를 1 증가시키면서 값을 찾아야 하는데, 그 과정에서 최대 길이인 회문을 찾는 과정을 보장하지 못하였다. 그래서 이중 for문에서 값을 하나하나 돌며, 해당 index값을 중앙값으로 하는 최대 회문의 길이를 찾고, 그 중 가장 긴 회문의 길이를 반환하였다. 이 과정에서 회문의 길이가 홀수, 짝수인 경우가 있는데, 홀수인 경우는 해당 index에서 일정값만큼 빼고 더해주며 회문을..

[SWEA] 1210 - Ladder (자바/Java)

사다리타기에 따라 정답으로 이어지는 시작점을 찾는 문제다. 정답에서부터 위로 올라가는 방식으로 구현하면 된다. 먼저 목적지의 row, col 좌표를 변수에 설정하고, 오른쪽이나 왼쪽 그리고 위로 올라가도록 구현한다. 이때 주의할 점은 위로 가는 것보다 오른쪽 왼쪽이 1인지를 먼저 검사해야 한다. 오른쪽, 왼쪽으로 가고 있다면 반대방향으로 돌아가서는 안된다. 이때 2를 고려하지 않아서 무한루프에 빠지는 문제가 발생했다. 그래서 dir 변수를 지정해줘서 오른쪽, 왼쪽으로 가는 경우는 반대방향이 아닐 경우에만 이동하도록 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_1210_Ladder { static int[][] ladder = ..

[SWEA] 6190 - 정곤이의 단조 증가하는 수 (자바/Java)

주어진 N개의 수에서 가능한 두 수의 곱 중, 가장 큰 단조 증가 수를 찾는 문제이다. 먼저 가능한 두 수의 곱을 이중 for문으로 찾고, 그 수가 단조 증가하는지를 찾으면 된다. 단조 증가 여부를 찾기 위해 정수형 숫자를 String으로 바꿔주고, 각 자리수를 돌며 앞의 자리수가 뒤의 자리수보다 클 경우 false를 return하였다. 또한, 단조 증가하는 수가 없을 경우 -1을 출력하기 위해, result의 초기값을 -1로 설정하였다. package SWEA0811; import java.util.Scanner; public class SWEA_6190_단조증가 { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..