[Java] SWEA 미로1 & Contact

1226 미로1 문제 링크

#1

import java.awt.*;
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=10;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            int[][] arr = new int[16][16];
            boolean[][] visited = new boolean[16][16];
            String a;
            for(int i=0; i<16; i++) {
                a = sc.next();
                for(int j=0; j<16; j++) {
                    arr[i][j] = a.charAt(j) - '0';
                }
            }

            Deque<Point> index = new ArrayDeque<>();
            index.add(new Point(1, 1));
            int answer = 0;

            Point now;
            while (!index.isEmpty()) {
                now = index.pollFirst();
                if(arr[now.x][now.y] == 3) {
                    answer = 1;
                    break;
                }

                if(!visited[now.x][now.y+1] && arr[now.x][now.y+1] == 0 || arr[now.x][now.y+1] == 3) {
                    visited[now.x][now.y+1] = true;
                    index.addLast(new Point(now.x, now.y+1));
                }
                if(!visited[now.x][now.y-1] && arr[now.x][now.y-1] == 0 || arr[now.x][now.y-1] == 3) {
                    visited[now.x][now.y-1] = true;
                    index.addLast(new Point(now.x, now.y-1));
                }
                if(!visited[now.x+1][now.y] && arr[now.x+1][now.y] == 0 || arr[now.x+1][now.y] == 3) {
                    visited[now.x+1][now.y] = true;
                    index.addLast(new Point(now.x+1, now.y));
                }
                if(!visited[now.x-1][now.y] && arr[now.x-1][now.y] == 0 || arr[now.x-1][now.y] == 3) {
                    visited[now.x-1][now.y] = true;
                    index.addLast(new Point(now.x-1, now.y));
                }
            }

            System.out.println("#" + test_case + " " + answer);
        }
    }
}

• BufferedWriter로 입력 받아서 풀려고 했는데 int N = br.nextLine(); 하니까 "" 입력되서 에러남
• 애초에 입력값에 ""인 줄이 없는데 왤까,,?
• 나중에 다시 시도해봐야지

1238 Contact 문제 링크

#1

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

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=10;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            Deque<Integer> start = new ArrayDeque<>();
            start.add(sc.nextInt());

            HashMap<Integer, Deque<Integer>> arr = new HashMap<>();
            int k, v;
            int maxV = 0;
            for(int i=0; i<N/2; i++) {
                k = sc.nextInt();
                v = sc.nextInt();
                if(!arr.containsKey(k)) {
                    arr.put(k, new LinkedList<>());
                }
                arr.get(k).add(v);
                maxV = Math.max(maxV, v);
            }

            int[] visited = new int[maxV+1];
            int level = 1;
            visited[start.peek()] = level;
            Deque<Integer> now;
            int n;
            while (arr.containsKey(start.peek())) {
                now = new LinkedList<>();
                while (!start.isEmpty() && arr.get(start.peekFirst())!=null) {
                    now.addAll(arr.get(start.pollFirst()));
                }
                level++;

                while (!now.isEmpty() && visited[now.peek()]==0){
                    n = now.pollFirst();
                    visited[n] = level;
                    start.addLast(n);
                }
            }

            int answer = 0;
            for(int i=0; i<visited.length; i++) {
                if(visited[answer] <= visited[i]) answer=i;
            }

            System.out.println("#"+test_case+" "+answer);
        }
    }
}

• dfs를 시도한 건데 잘못되도 단단히 잘못됨.

#2

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        //Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T;
        T=10;

        for(int test_case = 1; test_case <= T; test_case++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int[][] arr = new int[101][101];
            int from, to;
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N/2; i++) {
                from = Integer.parseInt(st.nextToken());
                to = Integer.parseInt(st.nextToken());
                arr[from][to] = 1;
            }

            int[] visited = new int[101];
            visited[start] = 1;
            Deque<Integer> list = new LinkedList<>();
            list.add(start);
            int answer = 0;
            int max = 0;
            int size;
            while (!list.isEmpty()) {
                size = list.size();
                max = 0;
                for(int j=0; j<size; j++) {
                    start = list.pollFirst();
                    for (int i = 0; i <= 100; i++) {
                        if (arr[start][i] == 1 && visited[i] == 0) {
                            list.addLast(i);
                            visited[i] = 1;
                            max = Math.max(max, i);
                        }
                    }
                }
                answer = max!=0 ? max : answer;
            }

            bw.write("#"+test_case+" "+answer+"\n");
            bw.flush();
        }
        bw.close();
    }
}

• 이거 하나 푸는데, 진짜 엄청 오래 걸림..
• 결국 dfs 문제였던 거 같은데
• dfs가 복잡해지니까 이 반복문 안에서 특정값을 구하는게
  빡세네