[백준 11403] 실버1 - 경로 찾기

www.acmicpc.net/problem/11403

11403번: 경로 찾기

풀이시간: 1시간

1. 개념

인접 행렬, 그래프 탐색

 

2. 풀이법

인접 행렬을 만든다. 시작 지점부터 연결된 지점을 재귀를 이용하여 계속 탐색한다.

만약 타깃을 찾으면 true를 리턴하고 재귀를 빠져나온다.

3. 코드

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

public class back_11403경로찾기 {
	static int n;
	static int list[][];
	static boolean visit[];
	public static void main(String[] args) {
		//for
			//for
				//if temp==1
					// list[i].add(j)
		//for
			//for
				//if go
					//ans[][]=1
		Scanner sc = new Scanner(System.in);
		n =sc.nextInt();
		int map[][] = new int[n][n];
		list = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				list[i][j] = sc.nextInt();
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				visit = new boolean[n];
				if(go(i,j)) {
					map[i][j] = 1;
				}
			}
		}
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}
	//go to, target
		//for from
			//visit == false
				//visit = true
				//if target == to
					//return true
				//if(go to)
	static boolean go(int from, int target) {
		for (int to = 0; to < n; to++) {
			if(list[from][to] == 1 && visit[to]==false) {
				if(target == to)
					return true;
				visit[to]= true;
				if(go(to, target)) {
					return true;
				}
			}
		}		
		return false;
	}
}

 

인접행렬을 만든다

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
 	 list[i][j] = sc.nextInt();
  }
}

 

두 노드가 서로 연결돼 있으면서, 아직 방문하지 않았다면 이동가능하다

if(list[from][to] == 1 && visit[to]==false)

 

목표지점과 만났다면, true를 리턴하고 재귀를 계속 빠져나온다

if(target == to)
	return true;