Karice의 여행 & 코딩 블로그

문제 설명

풀이

간단한 BFS문제, 익은 토마토를 기준으로 계속 Queue에 넣어주고 안익은 토마토를 지워주면 된다. BFS의 원리만 알면 정말 쉽게 풀 수 있는 문제

코드

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int M;
    static int[][] box;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static class Dot {
        int x;
        int y;
        int day;

        public Dot(int x, int y, int day) {
            this.x = x;
            this.y = y;
            this.day = day;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        box = new int[M][N];

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());

            for(int j=0; j<N; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs();
    }

    static void bfs() {
        Queue<Dot> q = new LinkedList<Dot>();
        int day = 0;

        // 토마토가 있는 좌표 찾아서 Queue에 넣기
        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(box[i][j] == 1)
                    q.offer(new Dot(i, j, 0));
            }
        }

        // bfs 시작
        while(!q.isEmpty()) {
            Dot dot = q.poll();
            day = dot.day;

            for(int i=0; i<4; i++) {
                int nx = dot.x + dx[i];
                int ny = dot.y + dy[i];

                if(0 <= nx && nx < M && 0 <= ny && ny < N) {
                    if(box[nx][ny] == 0) {
                        box[nx][ny] = 1;
                        q.add(new Dot(nx, ny, day+1));
                    }
                }
            }
        }

        // 토마토가 다 익었는지 확인
        if(checkTomato())
            System.out.println(day);
        else
            System.out.println(-1);
    }

    // box 배열에 0이 남아있다면 false, 아니면 true
    static boolean checkTomato() {
        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(box[i][j] == 0)
                    return false;
            }
        }

        return true;
    }
}

https://www.acmicpc.net/problem/7576

문제 설명

풀이

기본적인 BFS로 푸는 좌표 이동 문제. 그냥 나이트의 이동경로만 다르지 크게 다른 문제와 다를 것은 없음. 매우매우 쉬운 문제!

코드

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int T,N,x1,y1,x2,y2;
    static int[][] map;
    static int[][] visit;
    static int[] dx = {1,2,2,1,-1,-2,-2,-1};
    static int[] dy = {2,1,-1,-2,-2,-1,1,2};

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        while(T-- >0){
//            System.out.println(T+"번쨰");
            N = Integer.parseInt(br.readLine());
            map = new int[N+1][N+1];
            visit = new int[N+1][N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());

            if(x1 == x2 && y1 == y2){
                System.out.println(0);
            }
            else{
                bfs(x1,y1,x2,y2,N);
            }
        }


    }

    private static int bfs(int x1, int y1, int x2, int y2, int N) {
        Queue<int[]> que = new LinkedList<>();
        int c = 0;
        que.add(new int[] {x1,y1,c});
        visit[x1][y1] = 1;

        while (!que.isEmpty()) {
            int[] out = que.poll();
            int xx = out[0];
            int yy = out[1];
            int cnt = out[2];

            for(int i=0; i<8; i++){
                int dr = xx + dx[i];
                int dc = yy + dy[i];

                if( dr < 0 || dc < 0 || dr > N-1 || dc > N-1 || visit[dr][dc] == 1){
                    continue;
                }

                if(dr == x2 && dc == y2){
                    System.out.println(cnt+1);
                    return 0;
                }
                visit[dr][dc] = 1;
                que.add(new int[] {dr,dc,cnt+1});
            }
        }
        return 0;
    }
}

https://www.acmicpc.net/problem/7562

문제 설명

풀이

기본적으로 BFS로 풀어야된다는 것을 알고 있어야 한다.

그리고 생각보다 안복잡하고 간단한데, 안에 있는 공기는 신경안 써도 되는게, 밖에 있는 공기를 기준으로 BFS를 돌리면 된다는 것이다.

밖에 있는 빈칸을 기준으로 BFS를 돌리고, 경계면에 있는 치즈를 바로 0으로 바꿔주면서, 계속 Roop 시키면 끝!

배운것 : 복잡하게 생각하지 말고, 천천히 생각해보자

코드

import java.io.*;
import java.util.*;

public class Main {
	public static int N, M, cheese, cnt, time;
	public static int[][] map;
	public static boolean[][] v;
	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1)
					cheese++;
			}
		}
		while (cheese != 0) {
			time++;
			cnt = cheese;
			meltingCheese();
		}
		System.out.println(time);
		System.out.println(cnt);
	}

	public static void meltingCheese() {
		Queue<int[]> que = new LinkedList<int[]>();
		que.offer(new int[] { 0, 0 });
		v = new boolean[N][M];
		v[0][0] = true;
		while (!que.isEmpty()) {
			int[] cur = que.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || v[nx][ny]) continue;
				if (map[nx][ny] == 1) {
					cheese--;
					map[nx][ny] = 0;
				} else if (map[nx][ny] == 0) {
					que.offer(new int[] { nx, ny });
				}
				v[nx][ny] = true;
			}
		}
	}
}

문제 설명

풀이

BFS, DFS로 모두 풀 수 있는 문제이다. 일단 그래프 문제인 것은 바로 알 수 있고, 특별히 어느 것을 골라도 상관없을 듯하다.

풀이는, 일단 한 점을 잡고 쭉 DFS, BFS를 돌린다. 그러면 붙어있는 것들은 모두 visit = true가 될 것이고, 다음 탐색을 하면서 또 함수를 돌리고, 이렇게 반복하면 쉽게 풀 수 있다.

코드

BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int dx[] = {0,0,1,-1};
    private static int dy[] = {1,-1,0,0};
    private static int[] aparts = new int[25*25];
    private static int n;
    private static int apartNum = 0; //아파트 단지 번호의 수
    private static boolean[][] visited = new boolean[25][25]; //방문여부
    private static int[][] map = new int[25][25]; //지도

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        map = new int[n][n];
        visited = new boolean[n][n];

        //전체 사각형 입력 받기
        for(int i=0; i<n; i++){
            String input = sc.next();
            for(int j=0; j<n; j++){
                map[i][j] = input.charAt(j)-'0';
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == 1 && !visited[i][j]){
                    apartNum++;
                    bfs(i,j);
                }
            }
        }

        Arrays.sort(aparts);
        System.out.println(apartNum);

        for(int i=0; i<aparts.length; i++){
            if(aparts[i] == 0){
            }else{
                System.out.println(aparts[i]);
            }
        }

    }

    private static void bfs(int x, int y) {
        //2차원 LinkedList를 가진 큐 선언
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x,y});
        visited[x][y] = true;
        aparts[apartNum]++;

        while(!que.isEmpty()){

            //x, y 값을 받아오기 위한 방법
            int curX = que.peek()[0];
            int curY = que.peek()[1];
            que.poll();

            for(int i=0; i<4; i++){
                int nx = curX + dx[i];
                int ny = curY + dy[i];

                if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                    if(map[nx][ny] == 1 && !visited[nx][ny]){
                        que.add(new int[]{nx,ny});
                        visited[nx][ny] = true;
                        aparts[apartNum]++;
                    }
                }
            }
        }
    }
}

DFS

import java.io.*;
import java.util.Arrays;

public class Main {
    private static int num;
    private static int[][] map;
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n+2][n+2];
        for (int i = 1; i <= n; ++i) {
            char[] t = br.readLine().toCharArray();
            for (int j = 1; j <= n; ++j) {
                map[i][j] = t[j-1]-'0';
            }
        }
        br.close();
        num = 2;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (map[i][j] == 1) {
                    dfs(i, j);
                    ++num;
                }
            }
        }
        int[] nums = new int[num];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (map[i][j] !=  0) {
                    ++nums[map[i][j]-2];
                }
            }
        }
        Arrays.sort(nums);
        num = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                nums[num++] = nums[i];
            }
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(num));
        bw.newLine();
        for (int i = 0; i < num; ++i) {
            bw.write(String.valueOf(nums[i]));
            bw.newLine();
        }
        bw.close();
    }

    private static void dfs(int i, int j) {
        map[i][j] = num;
        if (map[i+1][j] == 1)
            dfs(i+1, j);
        if (map[i-1][j] == 1)
            dfs(i-1, j);
        if (map[i][j+1] == 1)
            dfs(i, j+1);
        if (map[i][j-1] == 1)
            dfs(i, j-1);
    }
}

https://www.acmicpc.net/problem/2667

문제 설명

풀이

기본적인 BFS 문제, 이런 경우 DFS로 할경우 오히려 늦어지는 경우가 많았음. BFS로 모든 경우의 수를 찾아가면 금방 찾아감!

코드

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new int[100001];
        if (N == M) {
            System.out.println(0);
        } else {
            System.out.println(bfs());
        }
    }

    private static long bfs() {
        Queue<Integer> que = new LinkedList<>();
        que.add(N);
        visit[N] = 1;

        while (!que.isEmpty()) {
            int out = que.poll();

            if (out == M) {
                return visit[out]-1;
            }
            if ( out * 2 <= 100000 && visit[out * 2] == 0){
                visit[out*2] = visit[out] + 1;
                que.add(out * 2);
            }
            if ( out + 1 <= 100000 && visit[out + 1] == 0 ){
                visit[out+1] = visit[out] + 1;
                que.add(out + 1);
            }
            if ( out - 1 >= 0 && visit[out -1] == 0 ){
                visit[out-1] = visit[out] + 1;
                que.add(out - 1);
            }
        }

        return -1;
    }
}

왜 틀린건지 모르는 내 해쉬를 사용한 코드...

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static long N,M;
    static HashMap<Long, Long> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Long.parseLong(st.nextToken());
        M = Long.parseLong(st.nextToken());
        if (N == M) {
            System.out.println(0);
        } else {
            System.out.println(bfs());
        }
    }

    private static long bfs() {
        Queue<long[]> que = new LinkedList<>();
        que.add(new long[] {N,0});

        while (!que.isEmpty()) {
            long[] out = que.poll();
            System.out.println(out[0]+"count : "+ out[1]);

            if (out[0] == M) return out[1];
            if ( out[0] * 2 <= M && !map.containsKey(out[0]*2)){
                map.put(out[0] * 2, out[1]+1);
                que.add(new long[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] + 1 <= M && !map.containsKey(out[0] + 1) ){
                map.put(out[0] + 1, out[1]+1);
                que.add(new long[] {out[0] + 1,out[1]+1});
            }
            if ( out[0] - 1 > 0 && !map.containsKey(out[0] - 1) ){
                map.put(out[0] - 1, out[1]+1);
                que.add(new long[] {out[0] - 1,out[1]+1});
            }
        }

        return -1;
    }
}

https://www.acmicpc.net/problem/1697

문제 설명

풀이

보자마자, DP, 와 BFS가 바로 생각났다. 그래서 바로 BFS로 풀었는데, 처음에는 visit을 해쉬맵(map)이 아닌 배열로 했다가 메모리 초과가 계속 떠서 더 찾아보니 HashMap으로 하면 더 빨라서 바로 바꾸었다.

그래도 계속해서 오답이 나오길래, Int에 문제가 있는 것 같아서 바로 Long으로 바꿔보니 통과했다.

역시 Input값의 범위도 항상 잘 봐야겠다.

코드

첫번째 코드 - 틀림

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int count;
    static int[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new int[M+1];
        count = 0;

        count = bfs();
        System.out.println(count);
    }

    private static int bfs() {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] {N,0});
        visit[N] = 0;

        while (!que.isEmpty()) {
            int[] out = que.poll();

            if (out[0] == M) return out[1] + 2;
            if ( out[0] * 2 <= M && visit[out[0]*2] == 0 ){
                visit[out[0] * 2] = out[1]+1;
                que.add(new int[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] * 10 + 1 <= M && visit[out[0] * 10 + 1] == 0 ){
                visit[out[0] * 10 + 1] = out[1]+1;
                que.add(new int[] {out[0] * 10 + 1,out[1]+1});
            }
        }
        return -1;
    }
}

완성된 코드 - 정답

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static long count;
    static HashMap<Long, Long> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = bfs();
        if(count == -1)
            System.out.println(count);
        else
            System.out.println(count+1);
    }

    private static long bfs() {
        Queue<long[]> que = new LinkedList<>();
        que.add(new long[] {N,0});

        while (!que.isEmpty()) {
            long[] out = que.poll();

            if (out[0] == M) return out[1];
            if ( out[0] * 2 <= M && !map.containsKey(out[0]*2)){
                map.put(out[0] * 2, out[1]+1);
                que.add(new long[] {out[0] * 2,out[1]+1});
            }
            if ( out[0] * 10 + 1 <= M && !map.containsKey(out[0] * 10 + 1) ){
                map.put(out[0] * 10 + 1, out[1]+1);
                que.add(new long[] {out[0] * 10 + 1,out[1]+1});
            }
        }
        return -1;
    }
}

문제 설명

풀이

수학적 해석을 이용한 문제라고 생각해서 머리를 굴려보았다.

알파벳 별로 (총 문자열길이 - 자릿수)를 알파벳 배열에 넣는다. 그러면 GCF는 각각 다음과 같이 들어간다.

G => alpha[6] = 100

C => alpha[2] = 10

F => alpha[5] = 1

이렇게 넣어서 내림차순으로 정렬한 뒤 9부터 차례대로 숫자를 대입해서 계산해주면 답이 나온다!!

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        //testcase 및 문자열 입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String [] arr = new String[n];
        int [] alpha = new int[26];
        for(int i=0; i<n; i++){
            arr[i] = sc.next();
        }


        for(int i=0; i<n; i++){
            int temp = (int)Math.pow(10,arr[i].length()-1);
            for(int j=0; j<arr[i].length(); j++){
                alpha[(int)arr[i].charAt(j)-65]+=temp;
                temp /=10;
            }
        }

        Arrays.sort(alpha);
        int index = 9;
        int sum =0;
        for(int i=alpha.length-1; i>=0; i--){
            if(alpha[i] == 0){
                break;
            }
            sum+= alpha[i]*index;
            index--;
        }
        System.out.println(sum);
    }
}

https://www.acmicpc.net/problem/1339

문제 설명

풀이

미로탐색하는 것은 뭐다? 대부분 BFS로 모든 길을 탐색해봐야한다. 가끔 DFS나 백트래킹이 있지만 대부분 BFS로 먼저 해보는게 경험상 좋은 것 같다. BFS로 방향을 정하면 큰 문제가 없다.

매번 문제 풀듯이, queue에 넣어주고 visit체크해주고, 옮기면서 타당성 체크해주고 통과하면 다시 queue에 넣어준다. 결국 BFS, DFS 판별하는게 키포인트!!

DFS로도 해봤는데 시간 초과가 뜸!! 문제별로 속도차이가 꽤 있는 듯

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int count;
    static int[][] map;
    static int[][] dis;
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        count = 0;
        map = new int[N+1][M+1];
        dis = new int[N+1][M+1];

        Queue<int[]> que = new LinkedList<int[]>();

        for(int i =0; i< N; i++){
            String[] input = br.readLine().split("");
            for(int j =0; j<M; j++){
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
//        for(int i =0; i< N; i++){
//            for(int j =0; j<M; j++){
//                System.out.print(map[i][j] + " ");
//            }
//            System.out.println();
//        }
        que.add(new int[] {0,0,0});
        dis[0][0] = 2;

        while (!que.isEmpty()) {
            int[] now =  que.poll();
            int x = now[0];
            int y = now[1];
            int cnt = now[2];
//            System.out.println("x축:"+y+" y축:"+x+" cnt:"+cnt);

            for(int z=0; z<4; z++){
                int cx = x + dx[z];
                int cy = y + dy[z];

                if(cx < 0 || cy < 0 || cx >= N || cy >= M || map[cx][cy] == 0 || dis[cx][cy] != 0){
                    continue;
                }
//                System.out.println("cx축:"+cy+" cy축:"+cx+" map:"+map[cx][cy]+" dis:"+dis[cx][cy]);
                dis[cx][cy] = 2;
                if (cx == N-1 && cy == M-1){
                    count = cnt+2;
                }
                que.add(new int[] {cx,cy,cnt+1});
            }
        }

        System.out.println(count);

    }
}

https://www.acmicpc.net/problem/2178

문제 설명

풀이

일단 DFS나 BFS 둘다 할 수 있다는 생각이 들었다. 하지만, 실제로 BFS를 통해 구현이 좋아보여서 그렇게 시작하게 되었다.

단순한 BFS 문제로, 갈수 있는 방향들을 계속 보내면서 queue에 넣고 도착지점에 도착할때까지 count를 증가시켜주면 된다. 

count를 인자로 계속 들고 있어야 되는게 핵심인듯

기초적인 BFS 문제!

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class knight {
    int r;
    int c;
    int cnt;
    knight(int r, int c, int cnt){
        this.r = r;
        this.c = c;
        this.cnt = cnt;
    }
}


public class Main {
    static int N;
    static int[][] map;
    static boolean[][] visit;
    static int r1,c1,r2,c2;
    static int[] dr = {-2,-2,0,0,2,2};
    static int[] dc = {-1,1,-2,2,-1,1};



    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        visit = new boolean[N+1][N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        r1 = Integer.parseInt(st.nextToken());
        c1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());

        bfs();
    }

    private static void bfs() {
        Queue<knight> que = new LinkedList<knight>();
        que.add(new knight(r1,c1,0));
        visit[r1][c1] = true;

        while(!que.isEmpty()){
            knight k = que.poll();

            for(int i =0; i<6; i++){
                int nr = k.r + dr[i];
                int nc = k.c + dc[i];

                if(nr <0 || nr > N || nc < 0 || nc > N || visit[nr][nc]){
                    continue;
                }
                if(nr == r2 && nc == c2){
                    System.out.println(k.cnt+1);
                    System.exit(0);
                }
                visit[nr][nc] = true;
                que.add(new knight(nr,nc,k.cnt+1));
            }
        }
        System.out.println(-1);
    }

}

https://www.acmicpc.net/problem/16948

문제 설명

풀이

모든 가지의 수를 구하는데 오름차순이라는 조건이 걸려있다.

그렇기에 일단 최심부까지 들어가는 DFS를 해야된다고 일단 생각이 났다.

그리고 백트래킹을 통해 각각의 경우의 수를 모두 파악하려고 하였다.

하지만 DFS 인자와 시작을 어떻게 해야할지 잘몰라서 방황하다가, start를 기준으로 계속 올라가게 만들면 된다는 생각을 했다. 그리고 for문은 dfs를 돌다가 마지막 조건에 도달했을때 해야된다는 것도 여기서 깨닫게 되었다.

백트래킹은 순차적으로 접근하여서 사전순으로 나열하기 좋음

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] lis;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        // 1. 값 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String input = br.readLine();
            if(input.equals("0")){
                return;
            }
            StringTokenizer st = new StringTokenizer(input);
            N = Integer.parseInt(st.nextToken());
            lis = new int[N+1];
            visit = new boolean[N+1];
            for(int i =0; i<N; i++){
                lis[i] = Integer.parseInt(st.nextToken());
            }

            dfs(0,0); //DFS어떻게 시작하는지 확실하게 정리!!!
            System.out.println();
        }
    }

    private static void dfs(int start, int depth) {
        if(depth == 6){
            for (int i=0; i<N; i++){
                if(visit[i]){
                    System.out.print(lis[i] + " ");
                }
            }
            System.out.println();
        }
        else{ //이부분 중요!!!
            for(int i=start; i< N; i++){
                visit[i] = true;
                dfs(i+1,depth+1);
                visit[i] = false;
            }
        }
    }
}

https://www.acmicpc.net/problem/6603