CLASS 3

1003

실버3

풀이

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

public class Main {

    static int[] fib0 = new int[41];
    static int[] fib1 = new int[41];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(bf.readLine());

        fib0[0] = 1;
        fib0[1] = 0;
        fib1[0] = 0;
        fib1[1] = 1;

        for (int i = 2; i < 41; i++) {
            fib0[i] = fib0[i - 1] + fib0[i - 2];
            fib1[i] = fib1[i - 1] + fib1[i - 2];
        }

        for (int i = 0; i < T; i++) {
            int a = Integer.parseInt(bf.readLine());
            System.out.println(fib0[a] + " " + fib1[a]);
        }
    }

}

1764

실버4

import java.util.*;

public class Main {

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

        String[] notHearName = new String[N];
        ArrayList<String> notHSName = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            notHearName[i] = sc.next();
        }

        Arrays.sort(notHearName);

        for (int i = 0; i < M; i++) {
            String notSeeName = sc.next();
            if (Arrays.binarySearch(notHearName, notSeeName) >= 0) {
                notHSName.add(notSeeName);
            }
        }

        int iter = notHSName.size();
        System.out.println(iter);

        Collections.sort(notHSName);
        for (int i = 0; i < iter; i++) {
            System.out.println(notHSName.get(i));
        }


    }
}

 C++의 vector처럼 배열을 사용하기 위해 ArrayList를 사용하였다. ArrayList는 일반 배열과 다르게 배열에 값을 추가하기 위해서 add()를 사용하고, 출력하기 위해서 get()을 사용한다.
 처음에 ArrayList를 일반 배열처럼 Arrays.sort()를 사용해서 정렬을 하려고 했으나, 컴파일 오류가 생겨서 Collections.sort()를 사용해 정렬을 하였다. 만약 내림차순으로 정렬을 하려면, Collections.sort(list, Collections.reverseOrder())를, 대소문자 구분없이 정렬하려면, Collections.sort(list, String.CASE_INSENSITIVE_ORDER), 내림차순은 Collections.sort(list, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER))로 하면 된다.

11723

실버5

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int M = Integer.parseInt(bf.readLine());
        boolean[] result = new boolean[21];

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            String op = st.nextToken();
            int num = 0;

            switch (op) {
                case "add":
                    num = Integer.parseInt(st.nextToken());
                    result[num] = true;
                    break;
                case "remove":
                    num = Integer.parseInt(st.nextToken());
                    result[num] = false;
                    break;
                case "check":
                    num = Integer.parseInt(st.nextToken());
                    if(result[num])
                        bw.write(1 + "\n");
                    else
                        bw.write(0 + "\n");
                    break;
                case "toggle":
                    num = Integer.parseInt(st.nextToken());
                    if (result[num]) {
                        result[num] = false;
                    } else {
                        result[num] = true;
                    }
                    break;
                case "all":
                    Arrays.fill(result, true);
                    break;
                case "empty":
                    Arrays.fill(result, false);
                    break;
            }
        }

        bw.flush();
        bw.close();
    }

}

1620

실버4

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

public class Main {

    public static boolean isInteger(String st) {
        try {
            Integer.parseInt(st);
            return true;
        } catch (NumberFormatException exception) {
            return false;
        }
    }   // String이 Integer인지 확인하는 함수

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<Integer, String> Dic = new HashMap<Integer, String>();
        HashMap<String, Integer> tmpDic = new HashMap<String, Integer>();
        for (int i = 1; i <= N; i++) {
            String a = bf.readLine();
            Dic.put(i, a);
            tmpDic.put(a, i);
        }

        for (int i = 0; i < M; i++) {
            String tmp = bf.readLine();
            if (isInteger(tmp)) {
                bw.write(Dic.get(Integer.parseInt(tmp)) + "\n");
            } else {
                bw.write(tmpDic.get(tmp) + "\n");
            }
        }

        bw.flush();
        bw.close();
    }

}

 결과를 출력하기 위해서 HashMap함수를 사용하였다. HashMap함수는 Key와 Value를 하나의 쌍으로 저장하는 방식으로 Key는 실질적인 value를 찾기 위한 이름의 역할을 한다. HashMap은 요소의 저장 순서를 유지하지 않고, Key는 중복을 허용하지 않는다.
 HashMap은 put Method를 사용해 저장하고, get Method를 사용해 값을 얻는다. 또한 ContainsKey를 이용해 Map에 Key가 있는지 결과를 리턴하고, remove를 사용해 삭제한다. 마지막으로 size를 이용해 갯수를 리턴한다.
 HashMap의 get의 시간복잡도는 O(1)로 for문을 사용해 값을 찾는 것 대신 이 방법을 사용하였다.

17219

실버4

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<String, String> map = new HashMap<String, String>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            map.put(st.nextToken(), st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            String tmp = bf.readLine();
            bw.write(map.get(tmp) + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 HashMap을 사용해 구현하였다.

1463

실버3

풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N + 1];

        if (N >= 2) {
            arr[2] = 1;
        }

        if (N >= 3) {
            arr[3] = 1;
        }

        for (int i = 4; i < N + 1; i++) {
            int[] tmp = new int[3];

            if (i % 2 == 0) {
                tmp[0] = arr[i / 2] + 1;
            }
            if (i % 3 == 0) {
                tmp[1] = arr[i / 3] + 1;
            }
            tmp[2] = arr[i - 1] + 1;

            Arrays.sort(tmp);

            for (int j = 0; j < 3; j++) {
                if (tmp[j] != 0) {
                    arr[i] = tmp[j];
                    break;
                }
            }

        }

        bw.write(arr[N] + "\n");
        bw.flush();
        bw.close();
    }
}

9095

실버3

import java.io.*;

public class Main {

    public static int factorial(int a) {
        int result = 1;
        for (int i = 1; i <= a; i++) {
            result = result * i;
        }

        return result;
    }

    public static int OneTwoThree(int n) {

        int sum = 0;
        for (int i = 0; i <= n; i++) {
            int temp = n - i;
            for (int j = 0; j <= temp / 2; j++) {
                int temp2 = temp - j * 2;
                if (temp2 % 3 == 0) {
                    int result = factorial(i + j + (temp2 / 3)) / (factorial(i) * factorial(j) * factorial(temp2 / 3));
                    sum += result;
                }
            }
        }

        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int T = Integer.parseInt(bf.readLine());
        for (int i = 0; i < T; i++) {
            bw.write(OneTwoThree(Integer.parseInt(bf.readLine())) + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 고등학교 확률과통계 시간에 배웠던 내용들을 사용하였다. 먼저, 하나의 숫자를 만들기 위한 1, 2, 3의 각 개수를 a, b, c개라고 하면 이 숫자들로 만들 수 있는 배열의 개수는 $\frac{(a + b + c)!}{a! \times b! \times c!}$ 이므로 이를 사용해 위 알고리즘을 구현하였다.

2630

실버2

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

public class Main {

    public static int N;
    public static int[][] Box;
    public static int White;
    public static int Blue;

    public static void Cut(int[][] arr) {
        boolean full = true;
        int color = arr[0][0];
        int iter = arr.length;

        for (int i = 0; i < iter; i++) {
            for (int j = 0; j < iter; j++) {
                if (arr[i][j] != color) {
                    full = false;
                }
            }
        }

        if (full) {
            if (color == 0) {
                White++;
            } else {
                Blue++;
            }
        } else {
            int[][] arr1 = new int[iter / 2][iter / 2];
            int[][] arr2 = new int[iter / 2][iter / 2];
            int[][] arr3 = new int[iter / 2][iter / 2];
            int[][] arr4 = new int[iter / 2][iter / 2];

            for (int i = 0; i < iter / 2; i++) {
                for (int j = 0; j < iter / 2; j++) {
                    arr1[i][j] = arr[i][j];
                }
            }

            for (int i = 0; i < iter / 2; i++) {
                for (int j = iter / 2; j < iter; j++) {
                    arr2[i][j - iter / 2] = arr[i][j];
                }
            }

            for (int i = iter / 2; i < iter; i++) {
                for (int j = 0; j < iter / 2; j++) {
                    arr3[i - iter / 2][j] = arr[i][j];
                }
            }

            for (int i = iter / 2; i < iter; i++) {
                for (int j = iter / 2; j < iter; j++) {
                    arr4[i - iter / 2][j - iter / 2] = arr[i][j];
                }
            }

            Cut(arr1);
            Cut(arr2);
            Cut(arr3);
            Cut(arr4);
        }


    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(bf.readLine());
        White = 0;
        Blue = 0;

        Box = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                Box[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Cut(Box);

        bw.write(White + "\n" + Blue);
        bw.flush();
        bw.close();
    }
}

 재귀를 이용하여 알고리즘을 설계하였다.

11403

실버1

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

public class Main {

    public static int N;
    public static int[][] graph;

    public static void next(int a, boolean[] visit) {
        for (int i = 0; i <= N; i++) {
            if (graph[a][i] == 1 && !visit[i]) {
                visit[i] = true;
                next(i, visit);
            }
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(bf.readLine());
        graph = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            for (int j = 1; j <= N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i <= N; i++) {
            boolean[] visit = new boolean[N + 1];
            for (int j = 1; j <= N; j++) {
                if (graph[i][j] == 1 && !visit[j]) {
                    visit[j] = true;
                    next(j, visit);
                }
            }

            for (int j = 1; j <= N; j++) {
                if (visit[j]) {
                    bw.write("1 ");
                } else {
                    bw.write("0 ");
                }
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();

    }
}

 그래프를 활용해서 위 문제를 풀었다.

2579

실버3

풀이

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(bf.readLine());
        int[] stair = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            stair[i] = Integer.parseInt(bf.readLine());
        }

        int[][] arr = new int[N + 1][N + 1];

        arr[0][1] = stair[1];

        if (N >= 2) {
            arr[0][2] = stair[2];
            arr[1][2] = arr[0][1] + stair[2];
        }

        if (N >= 3) {
            arr[1][3] = arr[0][1] + stair[3];
        }

        for (int i = 2; i < N; i++) {
            // i에서 i + 1으로 이동
            arr[i][i + 1] = arr[i - 2][i] + stair[i + 1];

            // i에서 i + 2로 이동
            if (i < N - 1) {
                int temp = arr[i-2][i] > arr[i-1][i] ? arr[i - 2][i] : arr[i - 1][i];
                arr[i][i + 2] = temp + stair[i + 2];
            }
        }

        // N = 1 때, default값으로 설정
        int result = arr[0][1];

        if (N > 1) {
            result = arr[N - 2][N] > arr[N - 1][N] ? arr[N - 2][N] : arr[N - 1][N];
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}

 위 풀이와 같이 Dynamic Programming 방식으로 접근하여 풀었다.

2606

실버3

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

public class Main {

    public static int N;
    public static int[][] graph;
    public static boolean[] check;

    public static void visit(int a) {
        for (int i = 1; i <= N; i++) {
            if (!check[i] && graph[a][i] == 1) {
                check[i] = true;
                visit(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(bf.readLine());
        graph = new int[N + 1][N + 1];
        check = new boolean[N + 1];
        int iter = Integer.parseInt(bf.readLine());
        for (int i = 0; i < iter; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        visit(1);

        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (check[i]) {
                count++;
            }
        }

        if (count == 0) {   // 1과 연결된 컴퓨터가 없을 경우
            count++;
        }

        bw.write((count - 1) + "\n");
        bw.flush();
        bw.close();
    }
}

 그래프의 기본 원리를 이용해 풀었다.

9375

실버3

풀이

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void Shin() throws IOException {
        int n = Integer.parseInt(bf.readLine());
        List<String> clothes = new ArrayList<>();   // 옷의 종류를 저장
        List<Integer> count = new ArrayList<>();    // 종류에 대한 옷의 갯수를 저장

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            String name = st.nextToken();
            String type = st.nextToken();

            if (clothes.contains(type)) {
                int temp = count.get(clothes.indexOf(type));
                temp++;
                count.set(clothes.indexOf(type), temp);
            } else {
                clothes.add(type);
                count.add(1);
            }
        }
        
        int result = 0;
        for (int i = 0; i < clothes.size(); i++) {
            result = result + count.get(i) * (1 + result);
        }

        bw.write(result + "\n");
    }

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(bf.readLine());
        for (int i = 0; i < N; i++) {
            Shin();
        }

        bw.flush();
        bw.close();
    }
}

1012

실버2

import java.io.*;
import java.util.BitSet;
import java.util.StringTokenizer;

public class Main {

    public static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int X;
    public static int Y;

    public static boolean[][] Farm;
    public static boolean[][] Visit;

    public static void Graph(int n) throws IOException {
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int b = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            Farm[a][b] = true;
        }
    }

    public static void next(int a, int b) {
        if (a - 1 >= 0) {
            if (!Visit[a - 1][b] && Farm[a - 1][b]) {
                Visit[a - 1][b] = true;
                next(a - 1, b);
            }
        }

        if (a + 1 < X) {
            if (!Visit[a + 1][b] && Farm[a + 1][b]) {
                Visit[a + 1][b] = true;
                next(a + 1, b);
            }
        }

        if (b - 1 >= 0) {
            if (!Visit[a][b - 1] && Farm[a][b - 1]) {
                Visit[a][b - 1] = true;
                next(a, b - 1);
            }
        }

        if (b + 1 < Y) {
            if (!Visit[a][b + 1] && Farm[a][b + 1]) {
                Visit[a][b + 1] = true;
                next(a, b + 1);
            }
        }

    }

    public static void main(String[] args) throws IOException {

        int T = Integer.parseInt(bf.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            Y = Integer.parseInt(st.nextToken());
            X = Integer.parseInt(st.nextToken());
            Farm = new boolean[X][Y];
            Visit = new boolean[X][Y];

            int A = Integer.parseInt(st.nextToken());
            Graph(A);

            int count = 0;

            for (int j = 0; j < X; j++) {
                for (int k = 0; k < Y; k++) {
                    if (Farm[j][k] && !Visit[j][k]) {
                        next(j, k);
                        count++;
                    }
                }
            }

            bw.write(count + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 한 위치에서 상하좌우를 모두 살핀 뒤, 이어진 곳이 없으면 count++를 해줌으로써 지렁이의 마릿수를 추가했다.

9461

실버3

풀이

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(bf.readLine());

        long[] tra = new long[101];
        tra[0] = 0;
        tra[1] = 1;
        tra[2] = 1;
        tra[3] = 1;
        tra[4] = 2;
        tra[5] = 2;

        for (int i = 6; i < 101; i++) {
            tra[i] = tra[i - 1] + tra[i - 5];
        }

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(bf.readLine());
            bw.write(tra[N] + "\n");
        }

        bw.flush();
        bw.close();
    }
}

11726

실버3

풀이

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bf.readLine());

        int[] arr = new int[1001];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;

        for (int i = 3; i <= n; i++) {
            arr[i] = (arr[i - 2] + arr[i - 1]) % 10007;
        }

        int result = arr[n];

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}

 10007로 나눈 나머지를 출력하라고 했지만, overflow가 발생할 수 있으므로, 각 계산마다 mod 연산을 해주었다.

21736

실버3

풀이

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

public class Main {

    public static int N;
    public static int M;

    public static int count;

    public static String[][] campus;
    public static boolean[][] visit;

    public static void findFriends(int x, int y) {

        if (visit[x][y]) {
            return;
        }   // 해당 좌표를 방문했다면 return

        visit[x][y] = true;

        if (campus[x][y].equals("P")) {
            count++;
        }
        if (x > 0 && !campus[x - 1][y].equals("X")) {
            findFriends(x - 1, y);
        }   // 상

        if (x < N - 1 && !campus[x + 1][y].equals("X")) {
            findFriends(x + 1, y);
        }   // 하

        if (y > 0 && !campus[x][y - 1].equals("X")) {
            findFriends(x, y - 1);
        }   // 좌

        if (y < M - 1 && !campus[x][y + 1].equals("X")) {
            findFriends(x, y + 1);
        }   // 우
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        count = 0;

        campus = new String[N][M];
        visit = new boolean[N][M];

        int curX = 0;
        int curY = 0;

        for (int i = 0; i < N; i++) {
            String temp = bf.readLine();
            String[] tempArr = temp.split("");

            for (int j = 0; j < M; j++) {
                campus[i][j] = tempArr[j];

                if (campus[i][j].equals("I")) {
                    curX = i;
                    curY = j;
                }
            }
        }

        findFriends(curX, curY);

        if (count == 0) {
            bw.write("TT");
        } else {
            bw.write(count + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 DFS를 해서 도연이의 친구를 찾아주었다.

14940

실버1

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

public class Main {

    public static int n;
    public static int m;

    public static int[][] Map;
    public static int[][] Distance;

    public static void BFS(Node node) {
        Queue<Node> qu = new LinkedList<>();

        qu.offer(node);

        while (!qu.isEmpty()) {
            Node cN = qu.poll();    // currentNode

            if (cN.x < n - 1 && Map[cN.x + 1][cN.y] > 0) {  // 상
                if (Distance[cN.x + 1][cN.y] > Distance[cN.x][cN.y] + 1) {
                    Distance[cN.x + 1][cN.y] = Distance[cN.x][cN.y] + 1;
                    qu.offer(new Node(cN.x + 1, cN.y));
                }
            }

            if (cN.x > 0 && Map[cN.x - 1][cN.y] > 0) {  // 하
                if (Distance[cN.x - 1][cN.y] > Distance[cN.x][cN.y] + 1) {
                    Distance[cN.x - 1][cN.y] = Distance[cN.x][cN.y] + 1;
                    qu.offer(new Node(cN.x - 1, cN.y));
                }
            }

            if (cN.y > 0 && Map[cN.x][cN.y - 1] > 0) {  // 좌
                if (Distance[cN.x][cN.y - 1] > Distance[cN.x][cN.y] + 1) {
                    Distance[cN.x][cN.y - 1] = Distance[cN.x][cN.y] + 1;
                    qu.offer(new Node(cN.x, cN.y - 1));
                }
            }

            if (cN.y < m - 1 && Map[cN.x][cN.y + 1] > 0) {  // 우
                if (Distance[cN.x][cN.y + 1] > Distance[cN.x][cN.y] + 1) {
                    Distance[cN.x][cN.y + 1] = Distance[cN.x][cN.y] + 1;
                    qu.offer(new Node(cN.x, cN.y + 1));
                }
            }


        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        Map = new int[n][m];
        Distance = new int[n][m];

        Node start = new Node(0, 0);

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < m; j++) {
                Map[i][j] = Integer.parseInt(st.nextToken());
                Distance[i][j] = Integer.MAX_VALUE;

                if (Map[i][j] == 2) {
                    start.x = i;
                    start.y = j;
                    Distance[i][j] = 0;
                } else if (Map[i][j] == 0) {
                    Distance[i][j]=0;
                }
            }
        }

        BFS(start);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (Distance[i][j] == Integer.MAX_VALUE) {
                    Distance[i][j] = -1;
                }
                bw.write(Distance[i][j] + " ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }

    public static class Node {
        int x;
        int y;

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

}