문제번호: 1012(유기농 배추)
풀이
- DFS를 이용해 지렁이가 있는 곳을 발견하면 DFS 호출
- 좌표가 배열을 초과하지 않도록 예외를 선언해주고 지렁이가 없는곳도 그냥 PASS
- 지렁이 있는곳을 지나가면 해당 좌표를 0으로 바꿔주고 계속 반복한다.
- 하나의 덩어리가 끝나면 count 1증가 시킴
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[][] arr;
static boolean[][] visited;
static int x = 0;
static int y = 0;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int count = 0;
public static void main(String[] args) throws IOException {
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine(), " ");
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
count = 0;
arr = new int[y][x];
for (int j = 0; j < n; j++) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[b][a] = 1;
}
for (int k = 0; k < y; k++) {
for (int l = 0; l < x; l++) {
if (arr[k][l] == 1) {
DFS(k, l);
count++;
}
}
}
System.out.println(count);
}
}
static void DFS(int X, int Y) {
for (int i = 0; i < 4; i++) {
int new_x = X + dx[i];
int new_y = Y + dy[i];
if (new_x < 0 || new_y < 0 || new_x >= y || new_y >= x) {
continue;
}
if (arr[new_x][new_y] == 0) {
continue;
}
arr[new_x][new_y] = 0;
DFS(new_x, new_y);
}
}
}문제번호: 1541(잃어버린 괄호)
풀이
- -를 기준으로 뒤에 있는 수들의 합을 -로 묶어주면 최소값을 만들 수 있다.
- 따라서 -를 기준으로 문자열을 일단 자른다.
- -를 기준으로 자르면 - 사이에 숫자와 +연산자가 섞여있기 때문에 +연산자로 또 자른다.
- +연산자로 자른 이후에 각각의 토큰을 더해준다
- 첫번째항을 제외하고 뒤에 있는 항은 모두 -로 묶어주면 되기 때문에 첫번째 항은 양수 나머지 항은 음수로 한다.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<Integer> answer = new ArrayList<>();
static int result = 0;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), "-");
ArrayList<String> arr = new ArrayList<>();
int i = 0;
while(st.hasMoreTokens()){
arr.add(st.nextToken());
StringTokenizer str = new StringTokenizer(arr.get(i),"+");
result = 0;
while(str.hasMoreTokens()){
result += Integer.parseInt(str.nextToken());
}
if(i == 0){
answer.add(result);
}
else{
answer.add(-(result));
}
i++;
}
int solution = 0;
for(int x = 0; x < answer.size(); x++){
solution += answer.get(x);
}
System.out.println(solution);
}
}문제번호: 1463(1로 만들기)
풀이
- Bottom-up 방식으로 접근
- dp[4]부터 전 인덱스에 1씩 더해주면서 배열을 만든다
- 만약 dp 인덱스가 3으로 나누어지고
해당인덱스 / 3의 인덱스 + 1이 dp[해당인덱스] 보다 작다면 최소값을 갱신해준다. - 만약 dp 인덱스가 2로 나누어지고
해당인덱스/ 2의 인덱스 + 1이 dp[해당인덱스]보다 작다면 최소값을 갱신해준다.
- 만약 dp 인덱스가 3으로 나누어지고
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[] dp;
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
dp = new int[1000001];
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
System.out.println(solution(n));
}
static int solution(int n) {
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 3 == 0 && dp[i] > dp[i/3] + 1) {
dp[i] = dp[i / 3] + 1;
}
if (i % 2 == 0 && dp[i] > dp[i/2] + 1) {
dp[i] = dp[i / 2] + 1;
}
}
return dp[n];
}
}문제번호: 1697(숨바꼭질)
풀이
- BFS 를 이용한다 -QUEUE
- 시작점에서 갈 수 있는 다음 단계는 3가지가 존재하며 다음 단계는 이전 단계 + 1을 해준다.
- QUEUE에 목적지가 들어올때까지 계속 채워준다.
- Arrayoutofindex때문에 엄청난 시간낭비를 했다. 예외를 잘 생각해보자.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static Queue<Integer> q = new LinkedList<Integer>();
static int[] visit = new int[100001];
static int answer;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
BFS(x, y);
System.out.println(answer);
}
static void BFS(int x, int y) {
q.add(x);
visit[x] = 0;
while (!q.isEmpty()) {
int num = q.poll();
if (num == y) {
break;
}
if (num - 1 >= 0 && visit[num - 1] == 0) {
visit[num - 1] = visit[num] + 1;
q.add(num - 1);
}
if (num + 1 < 100000 && visit[num + 1] == 0) {
visit[num + 1] = visit[num] + 1;
q.add(num + 1);
}
if (num * 2 <= 100000 && visit[num * 2] == 0) {
visit[num * 2] = visit[num] + 1;
q.add(num * 2);
}
}
answer = visit[y];
}
}문제번호: 1931(회의실 배정)
풀이
- 시간복잡도가 O(n^2)이 되면 시간초과가 발생한다
- 시작시간과 끝나는 시간중 끝나는 시간을 기준으로 정렬을 한다.
- 아무리 일찍 시작해도 끝나는 시간이 뒤면 손해임
- 끝나는 시간을 기준으로 정렬이 끝난후에 만약에 끝나는 시간이 동일한 경우
3시에 시작해서 3시에 끝낼 수 있는 일 /2시에 시작해서 3시에 끝낼 수 있는 일 이 있다고 할때 입력을3 3이 먼저pivot에 들어가면2 3은 그냥 통과된다.- 따라서 끝나는 시간이 동일한 경우에는 시작 시간에 맞춰 정렬을 해주어야 한다.
- 한번의 반복문동안 cnt를 통해 최대값을 출력한다.
- Comparator 활용 숙지하기.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<time> arr = new ArrayList<>();
static int cnt = 0;
static int pivot;
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine(), " ");
arr.add(new time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
System.out.println(solution(n));
}
static int solution(int n){
Collections.sort(arr, new Comparator<time>() {
@Override
public int compare(time o1, time o2) {
if(o1.y == o2.y){
return o1.x > o2.x ? 1 : -1;
}
return o1.y > o2.y ? 1 : -1;
}
});
pivot = 0;
for(int i = 0; i < n; i++){
if(pivot <= arr.get(i).x){
pivot = arr.get(i).y;
cnt++;
}
}
return cnt;
}
static class time{
int x;
int y;
public time(int x, int y){
this.x = x;
this.y = y;
}
}
}문제번호: 18870(좌표 압축)
풀이
- 좌표가 들어있는 배열을 두개 만든다
- 하나의 배열 좌표를 일단 정렬한다.
- 좌표를 정렬한 후에 Index 0부터 순회하면서 해당 값의 인덱스값이 좌표를 압축한 값이 된다.
- 정렬했으므로 앞에 있는 숫자 개수가 인덱스가 되므로
- HashMap을 이용하여 해당 값과 Index값을
put - 정렬 되지 않은 배열에서 앞에서부터 순회하며 해당 값의 index를 불러온다
- StringBuilder를 선언해서 한번에 출력해야 한다.
- for문으로 하나하나 출력하면 시간초과 뜸.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static HashMap<Integer, Integer> map = new HashMap<>();
static int[] answer;
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
answer = new int[n];
st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(st.nextToken());
answer[i] = arr[i];
}
solution(arr);
}
static void solution(int[] arr){
Arrays.sort(arr);
int pivot = Integer.MAX_VALUE;
int index = 0;
for(int i = 0; i < arr.length; i++){
if(pivot != arr[i]){
map.put(arr[i], index++);
pivot = arr[i];
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < answer.length; i++){
sb.append(map.get(answer[i]) + " ");
}
System.out.println(sb);
}
}문제번호: 7576(토마토)
풀이
- BFS로 접근
- 토마토가 있는 지점부터 큐에 넣고 다음 좌표들은 이전 좌표에 + 1을 해준다.
- 0인지 아닌지 체크하는 이유는 토마토가 있는 지점이 여러개 일 수 있기 때문에 가운데 지점에서 만남
- 배열을 순회하면서 최대값을 구한다.
- 처음 1에서 시작했기 때문에 1빼준다.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[][] arr;
static Queue<Point> qu = new LinkedList<>();
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr = new int[y][x];
for (int i = 0; i < y; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < x; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(BFS(arr));
}
static int BFS(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] == 1) {
qu.add(new Point(i, j));
}
}
}
while (!qu.isEmpty()) {
Point point = qu.poll();
for (int i = 0; i < 4; i++) {
int nextx = point.x + dx[i];
int nexty = point.y + dy[i];
if (nextx >= arr.length || nextx < 0 || nexty >= arr[0].length || nexty < 0 || arr[nextx][nexty] != 0) {
continue;
}
arr[nextx][nexty] = arr[point.x][point.y] + 1;
qu.add(new Point(nextx, nexty));
}
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j] == 0) {
return -1;
}
if (arr[i][j] > max) {
max = arr[i][j];
}
}
}
return max - 1;
}
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}문제번호: 2606(바이러스)
풀이
- BFS를 이용한다 - 큐 이용
- 1번 컴퓨터와 연결된 컴퓨터의 개수만 구하면 되므로 1번만 순회하면 된다.
배열 크기 주의
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[][] map;
static boolean[] check;
static int cnt = 0;
public static void main(String[] args) throws IOException{
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
map = new int[n+1][n+1];
check = new boolean[n+1];
for(int i = 0; i < m; i++){
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
map[x][y] = 1;
map[y][x] = 1;
}
System.out.println(solution());
}
static int solution(){
Queue<Integer> qu = new LinkedList<>();
check[1] = true;
qu.add(1);
while(!qu.isEmpty()){
int x = qu.poll();
for(int i = 1; i < map.length; i++){
if(map[x][i] == 1 && !check[i]){
check[i] = true;
qu.add(i);
cnt++;
}
}
}
return cnt;
}
}문제번호: 11724(연결 요소의 갯수)
풀이
- BFS를 이용해서 한번 순회할때마다 해당 점과 연결된 지점을 모두 체크해준다.
- 체크된 점은 cnt를 늘리지 않기 때문에 서로 연결된 집단의 갯수를 바로 알 수 있다.
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int node;
static int edge;
static int[][] arr;
static boolean[] check;
static int cnt = 0;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
node = Integer.parseInt(st.nextToken());
edge = Integer.parseInt(st.nextToken());
arr = new int[node + 1][node + 1];
check = new boolean[node + 1];
for(int i = 0; i < edge; i++){
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = 1;
arr[y][x] = 1;
}
for(int i = 1; i < node + 1; i++){
if(!check[i]){
bfs(i);
cnt++;
}
}
System.out.println(cnt);
}
static void bfs(int node){
Queue<Integer> qu = new LinkedList<>();
check[node] = true;
qu.add(node);
while(!qu.isEmpty()){
int x = qu.poll();
for(int i = 1; i < arr.length; i++){
if(!check[i] && arr[x][i] == 1){
qu.add(i);
check[i] = true;
}
}
}
}
}문제번호: 7569(토마토)
풀이
지난 7576 토마토 문제와 흡사하지만 다중배열을 사용해야 한다.
3차 배열에서 머리로 생각하느라 해맸다.
차원에 대해서 조금 더 생각해보자.
public class boj_7569 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int[][][] arr;
static Queue<newpoint> qu = new LinkedList<>();
static int[] dx = {1, -1, 0, 0, 0, 0};
static int[] dy = {0, 0, 1, -1, 0, 0};
static int[] dz = {0, 0, 0, 0, 1, -1};
static int cnt = 0;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
arr = new int[z][y][x];
for (int i = 0; i < z; i++) {
for (int j = 0; j < y; j++) {
st = new StringTokenizer(br.readLine(), " ");
for (int k = 0; k < x; k++) {
arr[i][j][k] = Integer.parseInt(st.nextToken());
}
}
}
System.out.println(BFS(x, y, z));
}
static int BFS(int x, int y, int z){
for (int i = 0; i < z; i++) {
for (int j = 0; j < y; j++) {
for (int k = 0; k < x; k++) {
if(arr[i][j][k] == 1){
qu.add(new newpoint(k, j, i));
}
}
}
}
while(!qu.isEmpty()){
newpoint po = qu.poll();
for (int i = 0; i < 6; i++) {
int nextx = po.x + dx[i];
int nexty = po.y + dy[i];
int nextz = po.z + dz[i];
if(nextx >= x || nextx < 0 || nexty >= y || nexty < 0 || nextz >= z || nextz < 0 || arr[nextz][nexty][nextx] != 0){
continue;
}
arr[nextz][nexty][nextx] = arr[po.z][po.y][po.x] + 1;
qu.add(new newpoint(nextx, nexty, nextz));
}
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < z; i++) {
for (int j = 0; j < y; j++) {
for (int k = 0; k < x; k++) {
if (arr[i][j][k] == 0) {
return -1;
}
if (arr[i][j][k] > max) {
max = arr[i][j][k];
}
}
}
}
return max - 1;
}
}
class newpoint {
int x;
int y;
int z;
public newpoint (int x, int y, int z){
this.x = x;
this.y = y;
this.z = z;
}
}
💻Backend Developer