[BOJ] 11403 경로 찾기

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

인접행렬을 주고 노드들이 서로 연결되어 있는지 찾는 문제이다.

Python

n = int(input())

adj = [list(map(int, input().split())) for _ in range(n)]

ans = [[0] * n for _ in range(n)]
for i in range(n):
  que = [i]
  idx = 0
  
  visited = [[0] * n for _ in range(n)]
  while idx < len(que):
    now = que[idx]
    idx += 1
    
    for next in range(n):
      if adj[now][next] and visited[now][next] == 0:
        que.append(next)
        ans[now][next] = visited[now][next] = 1
        
  for q in range(1, len(que)):
    ans[i][que[q]] = 1

for r in ans:
  print(" ".join(map(str, r)))

모든 점에 대해서 BFS를 돌려서 BFS 탐색 기록에 노드가 있다면 1로 표시해주는 작업을 했다. 점이 100개라서 가능했나보다.

Javascript

const input = require("fs").readFileSync(process.platform === "linux" ?
  "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number))

n = input[0][0]

const adj = input.slice(1)

const ans = Array.from({ length: n }, () => Array(n).fill(0));

for (let i = 0; i < n; i++) {
  let que = [i]
  let idx = 0
  let visited = Array.from({ length: n }, () => Array(n).fill(true))

  while (idx < que.length) {
    let now = que[idx++]

    for (let next = 0; next < n; next++) {
      if (adj[now][next] === 1 && visited[now][next]) {
        visited[now][next] = false
        que.push(next)
        ans[now][next] = 1
      }
    }
  }

  que.forEach((v, idx) => {
    if (idx > 0) ans[i][v] = 1
  })
}

ans.forEach(row => console.log(row.join(" ")));

백준에서 node.js 입력 받는 방법을 몰라서 한참을 헤맸다.

Java

import java.util.ArrayList;
import java.util.Scanner;

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

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] adj = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                adj[i][j] = scanner.nextInt();
            }
        }

        int[][] ans = new int[n][n];
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> queue = new ArrayList<>();
            queue.add(i);
            int idx = 0;

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

            while(idx < queue.size()){
                int now = queue.get(idx++);

                for(int next = 0;next< n;next++){
                    if(adj[now][next] == 1 && !visited[now][next]){
                        queue.add(next);
                        visited[now][next] = true;
                        ans[i][next] = 1;
                    }
                }
            }
        }

        for(int[] row:ans){
            for(int val:row){
                System.out.print(val + " ");
            }
            System.out.println();
        }

        scanner.close();
    }
}