[25/5월 3주차] 진행 내용 (05/26~ 06/01)

[kyuung09]

📅 이번 주 일정
날짜: 2025/05/26 ~ 2025/06/01

📋 진행 내용
Chapter5 탐색. 05-2 미로 탐색하기(2178)
Chapter5 탐색. 05-2 트리의 지름 구하기(1167)

📢 참고 사항
별도 커밋을 하지 않고, 이슈 내 댓글에 숙제를 올려주세요!
댓글 내 소스코드 작성 방법은 아래와 같습니다.

예시)

import java.util.Arrays;

public class Test{
    public static void main(String[] args) {
        System.out.println(Arrays.toString(players));
    }

    private static void swiping(String[] array, int i, int j) {
        String temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
복사해서 사용하세요!

🗣️ 질문/피드백
이번 주 일정이나 진행 내용에 대해 궁금한 점이나 피드백이 있다면 댓글로 남겨주세요.

[woooo96]

📋 문제 정보
Chapter5 탐색. 05-2 미로 탐색하기(2178)

🔍 풀이

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

public class Main {
static int N, M;
static int[][] maze;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0}; // 상, 하
static int[] dy = {0, 0, -1, 1}; // 좌, 우

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

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

    maze = new int[N][M];
    visited = new boolean[N][M];

    // 미로 정보 입력
    for (int i = 0; i < N; i++) {
        String line = br.readLine();
        for (int j = 0; j < M; j++) {
            maze[i][j] = line.charAt(j) - '0';
        }
    }

    bfs(0, 0);

    System.out.println(maze[N - 1][M - 1]);
}

static void bfs(int x, int y) {
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{x, y});
    visited[x][y] = true;

    while (!queue.isEmpty()) {
        int[] pos = queue.poll();
        int curX = pos[0];
        int curY = pos[1];

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

            if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
                if (!visited[nextX][nextY] && maze[nextX][nextY] == 1) {
                    visited[nextX][nextY] = true;
                    maze[nextX][nextY] = maze[curX][curY] + 1;
                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }
    }
}

}

📋 문제 정보
Chapter5 탐색. 05-2 트리의 지름 구하기(1167)

🔍 풀이
import java.io.;
import java.util.;

public class Main {
static class Node {
int vertex, weight;
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
}

static ArrayList<Node>[] tree;
static boolean[] visited;
static int maxDistance = 0;
static int farthestNode = 0;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int V = Integer.parseInt(br.readLine());

    tree = new ArrayList[V + 1];
    for (int i = 1; i <= V; i++) {
        tree[i] = new ArrayList<>();
    }

    for (int i = 0; i < V; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int from = Integer.parseInt(st.nextToken());
        while (true) {
            int to = Integer.parseInt(st.nextToken());
            if (to == -1) break;
            int weight = Integer.parseInt(st.nextToken());
            tree[from].add(new Node(to, weight));
        }
    }

    visited = new boolean[V + 1];
    dfs(1, 0);

    visited = new boolean[V + 1];
    dfs(farthestNode, 0);

    System.out.println(maxDistance);
}

static void dfs(int current, int sum) {
    visited[current] = true;

    if (sum > maxDistance) {
        maxDistance = sum;
        farthestNode = current;
    }

    for (Node next : tree[current]) {
        if (!visited[next.vertex]) {
            dfs(next.vertex, sum + next.weight);
        }
    }
}

}

[kyuung09]

📋 문제 정보
Chapter5 탐색. 05-2 미로 탐색하기(2178)

🔍 풀이

import java.util.*;

public class Main {
    static int N, M;
    static int[][] maze;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine(); // 개행 문자 제거

        maze = new int[N][M];
        visited = new boolean[N][M];

        // 미로 입력
        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < M; j++) {
                maze[i][j] = line.charAt(j) - '0';
            }
        }

        System.out.println(bfs(0, 0));
    }

    static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

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

                // 범위 벗어나면 무시
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;

                // 이동할 수 없거나 방문한 곳이면 무시
                if (maze[nx][ny] == 0 || visited[nx][ny])
                    continue;

                // 거리 갱신 및 방문 체크
                maze[nx][ny] = maze[cx][cy] + 1;
                visited[nx][ny] = true;
                queue.offer(new int[]{nx, ny});
            }
        }

        // 도착지점의 거리 리턴
        return maze[N - 1][M - 1];
    }
}

📋 문제 정보
Chapter5 탐색. 05-2 트리의 지름 구하기(1167)

🔍 풀이

import java.util.*;

public class Main {
    static class Node {
        int to, weight;
        Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static List<Node>[] tree;
    static boolean[] visited;
    static int maxDistance = 0;
    static int farthestNode = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        tree = new ArrayList[V + 1];

        for (int i = 1; i <= V; i++) {
            tree[i] = new ArrayList<>();
        }

        // 간선 정보 입력
        for (int i = 0; i < V; i++) {
            int from = sc.nextInt();
            while (true) {
                int to = sc.nextInt();
                if (to == -1) break;
                int weight = sc.nextInt();
                tree[from].add(new Node(to, weight));
            }
        }

        // 1차 DFS: 아무 노드에서 가장 먼 노드 찾기
        visited = new boolean[V + 1];
        dfs(1, 0);

        // 2차 DFS: 가장 먼 노드에서 또 DFS => 트리의 지름
        visited = new boolean[V + 1];
        maxDistance = 0;
        dfs(farthestNode, 0);

        System.out.println(maxDistance);
    }

    static void dfs(int node, int distance) {
        visited[node] = true;

        if (distance > maxDistance) {
            maxDistance = distance;
            farthestNode = node;
        }

        for (Node neighbor : tree[node]) {
            if (!visited[neighbor.to]) {
                dfs(neighbor.to, distance + neighbor.weight);
            }
        }
    }
}

[Sangtriever]

📋 문제 정보
Chapter5 탐색. 미로 탐색하기(2178)

🔍 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Num2178 {

    static int[][] map;
    static boolean[][] visited;
    static int n, m;

    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};

    static class Point {
        int x, y;

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

    public static void main(String[] args) throws IOException {
        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];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = row.charAt(j) - '0';
            }
        }

        visited[0][0] = true;
        bfs(new Point(0, 0));

        System.out.println(map[n - 1][m - 1]);
    }

    static void bfs(Point start) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            for (int direction = 0; direction < 4; direction++) {
                int nextX = current.x + dx[direction];
                int nextY = current.y + dy[direction];

                if (!isInBounds(nextX, nextY) || visited[nextX][nextY] || map[nextX][nextY] == 0) {
                    continue;
                }

                queue.offer(new Point(nextX, nextY));
                visited[nextX][nextY] = true;
                map[nextX][nextY] = map[current.x][current.y] + 1;
            }
        }
    }

    static boolean isInBounds(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m;
    }
}

📋 문제 정보
Chapter5 탐색. 05-2 트리의 지름 구하기(1167)

🔍 풀이

import java.util.*;

public class Num1167 {

    static ArrayList<Point>[] graph;
    static boolean[] visited;
    static int maxDistance = 0;
    static int farthestNode = 0;

    static class Point {
        int to;
        int weight;

        public Point(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

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

        int n = scan.nextInt();
        graph = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            int from = scan.nextInt();
            while (true) {
                int to = scan.nextInt();
                if (to == -1) break;
                int weight = scan.nextInt();
                graph[from].add(new Point(to, weight));
            }
        }

        visited = new boolean[n + 1];
        dfs(1, 0);

        visited = new boolean[n + 1];
        maxDistance = 0; // 초기화
        dfs(farthestNode, 0);

        System.out.println(maxDistance);
    }

    static void dfs(int current, int distance) {
        if (distance > maxDistance) {
            maxDistance = distance;
            farthestNode = current;
        }

        visited[current] = true;

        for (Point neighbor : graph[current]) {
            if (!visited[neighbor.to]) {
                dfs(neighbor.to, distance + neighbor.weight);
            }
        }
    }

}

[leemeo3]

📋 문제 정보
Chapter5 탐색. 미로 탐색하기(2178)

🔍 풀이

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

public class P027미로탐색하기 {
    static int arr[][];
    static boolean visited[][];
    static int []dx = {1, 0, -1, 0};
    static int []dy = {0, 1, 0, -1};
    static int n,m;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        visited = new boolean[n][m];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }
        BFS(0,0);
        System.out.println(arr[n - 1][m - 1]);
    }

    private static void BFS(int i, int j) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{i, j});
        visited[i][j] = true;
        while(!que.isEmpty()) {
            int now[] = que.poll();

            for(int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < m) {
                    if(arr[x][y] != 0 && !visited[x][y]) {
                        visited[x][y] = true;
                        arr[x][y] = arr[now[0]][now[1]] + 1;
                        que.add(new int[] {x,y});
                    }
                }
            }
        }
    }
}

📋 문제 정보
Chapter5 탐색. 05-2 트리의 지름 구하기(1167)

🔍 풀이

import java.util.*;

public class P028트리의지름구하기 {
    static boolean visited[];
    static int[] distance;
    static ArrayList<Edge>[] A;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        A = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < N; i++) {
            int S = sc.nextInt();
            while (true) {
                int E = sc.nextInt();
                if (E == -1) {
                    break;
                }
                int V = sc.nextInt();
                A[S].add(new Edge(E, V));
            }
        }
        distance = new int[N + 1];
        visited = new boolean[N + 1];
        BFS(1);
        int Max = 1;
        for (int i = 2; i <= N; i++) {
            if (distance[Max] < distance[i]) {
                Max = i;
            }
        }
        distance = new int[N + 1];
        visited = new boolean[N + 1];
        BFS(Max);
        Arrays.sort(distance);
        System.out.println(distance[N]);
    }

    private static void BFS(int index) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(index);
        visited[index] = true;
        while (!queue.isEmpty()) {
            int now_node = queue.poll();
            for (Edge i : A[now_node]) {
                int e = i.e;
                int v = i.value;
                if (!visited[e]) {
                    visited[e] = true;
                    queue.add(e);
                    distance[e] = distance[now_node] + v;
                }
            }
        }
    }

    static class Edge {
        int e;
        int value;
        public Edge(int e, int value) {
            this.e = e;
            this.value = value;
        }
    }
}

[eunsol-an]

📋 문제 정보
문제 제목: Chapter5 탐색. 05-2 미로 탐색하기(2178)

🔍 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static boolean[][] visited;
    static int[][] A;
    static int N, M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j = 0; j < M; j++) {
                A[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }
        BFS(0, 0);
        System.out.println(A[N - 1][M - 1]);
    }

    public static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] { i, j });
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            visited[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if (x >= 0 && y >= 0 && x < N && y < M) {
                    if (A[x][y] != 0 && !visited[x][y]) {
                        visited[x][y] = true;
                        A[x][y] = A[now[0]][now[1]] + 1;
                        queue.add(new int[] { x, y });
                    }
                }
            }
        }
    }
}

---

📋 문제 정보
문제 제목 : Chapter5 탐색. 05-2 트리의 지름 구하기(1167)

🔍 풀이

import java.util.*;

public class Main {
    static boolean[] visited;
    static int [] distance;
    static ArrayList<Edge>[] A;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        A = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<>();
        }
        for (int i = 0; i < N; i++) {
            int S = sc.nextInt();
            while (true) {
                int E = sc.nextInt();
                if (E == -1) break;
                int V = sc.nextInt();
                A[S].add(new Edge(E, V));
            }
        }
        distance = new int[N+1];
        visited = new boolean[N+1];
        BFS(1);
        int Max = 1;
        for (int i = 2; i <= N; i++) {
            if (distance[Max] < distance[i])
                Max = i;
        }
        distance = new int[N+1];
        visited = new boolean[N+1];
        BFS(Max);
        Arrays.sort(distance);
        System.out.println(distance[N]);
    }

    private static void BFS(int index) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;
        while (!queue.isEmpty()) {
            int nowNode = queue.poll();
            for (Edge i : A[nowNode]) {
                int e = i.e;
                int v = i.value;
                if (!visited[e]) {
                    visited[e] = true;
                    queue.add(e);
                    distance[e] = distance[nowNode] + v;
                }
            }
        }
    }
}
class Edge {
    int e;
    int value;

    public Edge(int e, int value) {
        this.e = e ;
        this.value = value;
    }
}

---

[hongdangmoo49]

📋 문제 정보
Chapter5 탐색. 05-2 미로 탐색하기(2178)

🔍 풀이

interface MazeInput {
    n: number;
    m: number;
    maze: string[];
  }
  
  interface MazeOutput {
    minDistance: number;
  }
  
  interface Position {
    row: number;
    col: number;
    distance: number;
  }
  
  function solveMaze(input: MazeInput): MazeOutput {
    const { n, m, maze } = input;
    
    const grid: number[][] = maze.map(row => 
      row.split('').map(cell => parseInt(cell))
    );
    
    const visited: boolean[][] = Array.from({ length: n }, () => 
      new Array(m).fill(false)
    );
    
    const directions = [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1]
    ];
    
    const queue: Position[] = [];
    
    queue.push({ row: 0, col: 0, distance: 1 });
    visited[0][0] = true;
    
    while (queue.length > 0) {
      const current = queue.shift()!;
      const { row, col, distance } = current;
      
      if (row === n - 1 && col === m - 1) {
        return { minDistance: distance };
      }
      
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;
        
        if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= m) {
          continue;
        }
        
        if (grid[newRow][newCol] === 1 && !visited[newRow][newCol]) {
          visited[newRow][newCol] = true;
          queue.push({
            row: newRow,
            col: newCol,
            distance: distance + 1
          });
        }
      }
    }
    
    return { minDistance: -1 };
  }

📋 문제 정보
문제 제목 : Chapter5 탐색. 05-2 트리의 지름 구하기(1167)

🔍 풀이

interface TreeDiameterInput {
    v: number;
    edges: number[][];
  }
  
  interface TreeDiameterOutput {
    diameter: number;
  }
  
  interface Edge {
    to: number;
    weight: number;
  }
  
  interface DFSResult {
    farthestNode: number;
    maxDistance: number;
  }
  
  function solveTreeDiameter(input: TreeDiameterInput): TreeDiameterOutput {
    const { v, edges } = input;
    
    const graph: Edge[][] = Array.from({ length: v + 1 }, () => []);
    
    for (let i = 0; i < edges.length; i++) {
      const edgeInfo = edges[i];
      const from = i + 1;
      
      for (let j = 0; j < edgeInfo.length - 1; j += 2) {
        const to = edgeInfo[j];
        const weight = edgeInfo[j + 1];
        
        if (to === -1) break;
        
        graph[from].push({ to, weight });
      }
    }
    
    function dfs(start: number): DFSResult {
      const visited = new Array(v + 1).fill(false);
      let maxDistance = 0;
      let farthestNode = start;
      
      function dfsRecursive(node: number, distance: number): void {
        visited[node] = true;
        
        if (distance > maxDistance) {
          maxDistance = distance;
          farthestNode = node;
        }
        
        for (const edge of graph[node]) {
          if (!visited[edge.to]) {
            dfsRecursive(edge.to, distance + edge.weight);
          }
        }
      }
      
      dfsRecursive(start, 0);
      return { farthestNode, maxDistance };
    }
    
    const firstDFS = dfs(1);
    
    const secondDFS = dfs(firstDFS.farthestNode);
    
    return { diameter: secondDFS.maxDistance };
  }
  
  function parseTreeInput(lines: string[]): TreeDiameterInput {
    const v = parseInt(lines[0]);
    const edges: number[][] = [];
    
    for (let i = 1; i <= v; i++) {
      const parts = lines[i].split(' ').map(num => parseInt(num));
      edges.push(parts.slice(1));
    }
    
    return { v, edges };
  }