[JAVA] 백준 골드 모음(13023 ABCDE, 2170 선 긋기, 1976 여행 가자, 9251 LCS, 11729 하노이 탑 이동 순서)

 

 

 

13023 ABCDE

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

13023번: ABCDE

 

• 친구관계와 관련되어 있어서 union-find인가 생각도 들었지만, A-B-C-D-E 로 이어져야하고, 네트워크와는 관련이 없기 때문에 다른 방식으로 풀어야한다는 걸 느꼈다
• 4만큼 떨어져있다면 촌수계산처럼 bfs로 푸는 게 맞나 싶었지만, visit관리를 어떻게 해야할 지 몰라 dfs로 풀었다.

 

class Man {
	int num;
	int count;
	
	public Man(int num, int count) {
		this.num = num;
		this.count = count;
	}
}

public class Solution {
	static List<Integer>[] arr;
	static boolean exist = false;
	static boolean[] visit;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int manCnt = Integer.parseInt(st.nextToken());
        int relationCnt = Integer.parseInt(st.nextToken());
        
        arr = new ArrayList[manCnt+1];
        visit = new boolean[manCnt+1];
        
        for (int i =0; i<manCnt+1; i++) {
        	arr[i] = new ArrayList<>();
        }
        
        for (int i =0; i<relationCnt; i++) {
        	st = new StringTokenizer(br.readLine());
        	int man1 = Integer.parseInt(st.nextToken());
        	int man2 = Integer.parseInt(st.nextToken());
        	
        	arr[man1].add(man2);
        	arr[man2].add(man1);
        }

        for (int i =0; i<manCnt; i++) {
        	visit[i] = true;
            dfs(i, 0);
            visit[i] = false;
        }

        if (exist) {
        	System.out.println(1);
        } else {
        	System.out.println(0);        	
        }
    }
    
    static void dfs(int num, int count) {
    	if (count >= 4) {
    		exist = true;
    		return;
    	}
    	for (int friendNum: arr[num]) {
    		if (visit[friendNum] == false) {
    			visit[friendNum] = true;
    			dfs(friendNum, count+1);
    			visit[friendNum] = false;  
    		}
    		if (exist == true)
				return;
    	}
    }
}

 

 

 

2170 선 긋기 - 골드5

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

2170번: 선 긋기

 

• 도화지라고 해서 2차원인줄 알았는데 그냥 자 위에서 움직이는거였음
• 시작점을 오름차순으로 정렬하고, 스택에 넣고빼면서 구현하면 될 것 같다
• 시작점을 기준으로 오름차순 정렬을 했기 때문에 그냥 push를 해도 앞에 선과 겹칠 일이 없다

 

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());
    int[][] lines = new int[cnt][2]; //시작점 끝점

    //입력받기
    for (int i=0; i<cnt; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      lines[i][0] = Integer.parseInt(st.nextToken());
      lines[i][1] = Integer.parseInt(st.nextToken());
    }

    //오름차순 정렬
    Arrays.sort(lines, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[0] - o2[0];
      }
    });

    Stack<int[]> stack = new Stack<>();
    stack.add(lines[0]);

    for (int i =1; i<lines.length; i++) {
      int[] curr = lines[i];
      int[] peek = stack.peek();
      if (isOverlap(curr, peek)) {
        stack.pop();
        stack.push(new int[]{Math.min(peek[0], curr[0]), Math.max(peek[1], curr[1])});
      } else {
        stack.push(curr);
      }
    }

    int result = 0;
    while (!stack.isEmpty()) {
      int[] pop = stack.pop();
      result += (pop[1] - pop[0]);
    }

    System.out.println(result);
  }

  private static boolean isOverlap(int[] curr, int[] peek) {
    //curr[0] 이 peek[0]과 peek[1] 사이에 있는지 확인
    //curr[1] 이 peek[0]과 peek[1] 사이에 있는지 확인
    return (peek[0] <= curr[0] && curr[0] <= peek[1]) || (peek[0] <= curr[1] && curr[1] <= peek[1]);
  }
}

• 2차원 배열을 만들어 입력을 받는다. line[i][0]은 시작점이고 line[i][1]은 끝점이다
• 2차원 배열 line을 시작점(0열)을 기준으로 정렬한다
• Stack을 만들어 line배열의 첫 번째 값을 넣는다
• 이후 for문으로 line배열에 값을 하나씩 뺀다
  • stack의 peek()을 현재 값과 비교하여 겹치는지 확인한다
  • 겹치면 stack을 pop하고, 새로운 갱신값을 넣는다([1 3], [2 5] 면 [1 5]로 갱신)
  • 겹치지 않으면 그냥 stack에 push를 한다
• 마지막엔 stack에 있는 모든 선을 빼서 길이를 더하고 출력한다

 

 

1976 여행 가자 - 골드4

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

1976번: 여행 가자

 

• 그냥 주어진 경로 값들이 서로 연결되어있는지 확인하면 될 것 같다
• 아이디어가 떠오르지 않아서 그냥 union-find 알고리즘을 사용해보려고 한다

 

public class Main {
  static int[] parent;
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int countryCnt = Integer.parseInt(br.readLine());
    int tripCnt = Integer.parseInt(br.readLine());

    parent = new int[countryCnt+1];
    for (int i =1; i<parent.length; i++)
      parent[i] = i;

    for (int i =1; i<=countryCnt; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int j=1; j<=countryCnt; j++) {
        if (st.nextToken().equals("1")) {
          int parentI = find(i);
          int parentJ = find(j);
          if (parentI != parentJ)
            parent[parentI] = parentJ;
        }
      }
    }

    StringTokenizer st= new StringTokenizer(br.readLine());
    int ancestor = 0;
    boolean canTrip = true;
    for (int i=0; i<tripCnt; i++) {
      if (ancestor == 0) {
        ancestor = find(Integer.parseInt(st.nextToken()));
      } else {
        int tmp = find(Integer.parseInt(st.nextToken()));
        if (ancestor != tmp) {
          canTrip = false;
          break;
        }
      }
    }

    if (canTrip)
      System.out.println("YES");
    else
      System.out.println("NO");
  }

  static int find(int tmp) {
    if (parent[tmp] == tmp)
      return tmp;

    parent[tmp] = find(parent[tmp]);
    return parent[tmp];
  }
}

• 만약 이어진 경로라면 find하여 parent를 연결한다
• find할 때는 최적화가 이루어짐
• 그냥 union-find를 쓴거 빼곤 특별한 게 없다

 

다른 풀이가 있나 찾아봤는데 대부분 union-find를 사용하셨다. 이 문제는 정점 간의 관계가 핵심이기 때문에 경로를 저장할 필요는 없음. 풀이법이 정형화가 되어있는 것 같다

 

 

 

9251 LCS

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

9251번: LCS

• LIS 알고리즘인 줄 알았는데, 공통부분수열이라서 고민했다
• 최대 1000글자라서 브루트포스는 무리일 것 같은데, dp인가?
• 한 번 적어봤다

 

dp맞네..

 

풀이법

• 행우선으로 2차원 배열을 채운다
• 만약 현재 위치의 열에 해당하는 값과 행에 해당하는 값이 같으면, i-1 j-1에 +1한 값을 나에게 넣는다
  • 예를들어 ACA와 CA를 비교하는 상황이라면 맨 마지막 값이 A == A 로 동일하다
  • 그러면 AC와 C인 경우 최대공통부분수열에 1을 더하면 내 값이 된다
• 만약 같지 않다면 i-1, j  와 i, j-1 값 중 최댓값을 나한테 대입한다

 

풀이법

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = " " + br.readLine();
        String b = " " + br.readLine();

        int[][] arr = new int[a.length()][b.length()];
        for (int i=1; i< arr.length; i++) {
            for (int j=1; j<arr[0].length; j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    arr[i][j] = arr[i-1][j-1]+1;
                } else {
                    arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
                }
            }
        }

        System.out.println(arr[a.length()-1][b.length()-1]);
    }
}

 

 

 

11729 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

 

• dp라고 생각했는데, 이동 순서 자체를 출력해야해서 재귀로 푸는 게 맞았다
• 1번째에 있는 4개의 탑을 3번째로 옮기려면 다음과 같은 순서로 옮긴다
  1. 3개의 탑을 2번째로 모두 옮긴다(123 순서로)
  2. 1번째에 있는 원판을 3번째로 옮긴다
  3. 2번째에 있는 3개의 탑을 3번째로 옮긴다
• 이런 느낌으로 재귀함수를 만들고 출력하는 코드를 만들면 된다

 

풀이

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int resultCnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

        hanoi(cnt, 1, 3);

        System.out.println(resultCnt);
        System.out.print(sb);
    }

    private static void hanoi(int num, int start, int end) {
        if (num == 1) {
            sb.append("" + start + " " + end + "\n");
        } else {
            int mid = 1;
            if (start != 2 && end != 2) {
                mid = 2;
            } else if (start != 3 && end != 3) {
                mid = 3;
            }

            hanoi(num-1, start, mid);
            sb.append("" + start + " " + end + "\n");
            hanoi(num-1, mid, end);
        }

        resultCnt++;
    }
}