고양멍멍이

[문제링크]

0. 슬라이딩 윈도우로, 다음 초밥을 넣고, 첫 초밥은 빼가며 종류를 센다 (큐 사용)

  - 회전초밥벨트이므로, 시작한 K개의 초밥이 마지막 초밥에 이어진다 

  - [시작부분] - [나머지] - [시작부분] 의 순서로 저장해서 처리

1. end포인터를 1씩 늘려가며 k개의 초밥을 받고, 종류를 센다

2. end포인터가 N+k가 될 때까지, end포인터의 초밥을 포함시키고, fst포인터의 초밥을 내보내는것을 반복한다

3. 위 과정중 구해진 가장 큰 cnt를 출력

개선점 : 모든 입력을 받고 시작하게 되면, 초밥을 큐로 관리할 필요가 없다

  - 큐 대신 포인터변수 2개만 사용해도 된다.

  - 반영함

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		//d+1개의 배열 생성.
		int[] count = new int[d+1];
		count[Integer.parseInt(st.nextToken())]=1;//쿠폰은 항상 먹는다
		
		//초밥 종류 cnt변수
		int cnt=1, max=0;
		
		//처음 K개 저장할 배열 생성
		int[] saveFst = new int[N+k];
		for (int i = 0; i < N; i++) {
			saveFst[i]=Integer.parseInt(br.readLine());;
			if(i<k)saveFst[N+i]=saveFst[i];
		}
		
		int fst=0, end=0;
		for (; end < k; end++) {
			if(++count[saveFst[end]]==1)cnt++;
		}
		max=cnt;
		for (; end < N+k; end++) {
			if(++count[saveFst[end]]==1)cnt++;
			
			if(--count[saveFst[fst++]]==0)cnt--;
			
			if(max<cnt)max=cnt;
		}
		System.out.println(max);
		
	}
}

[문제링크]

0. 내부 공기엔 인접해도 녹지 않으므로, 외곽 공기에 대해서만 bfs를 진행.

  - 0,0은 항상 밖의 공기이다

1. 0,0을 시작점으로, 외곽 공기를 bfs로 순회한다

  - 치즈를 처음 만나면, 표시만 한다

  - 치즈를 2번째로 만나면, 제거 대상 치즈로 판단, 저장한다

2. 1번에서 저장된 제거대상 치즈를 제거한다

3. 위 과정을 치즈가 없어질때까지 반복한다

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

public class Main{
	static int[] dx= {1,0,-1,0};
	static int[] dy= {0,1,0,-1};
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[][]map = new int[n][m];
		int chCnt=0;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < m; j++) {
				map[i][j]=pint(st.nextToken());
				if(map[i][j]==1)chCnt++;
			}
		}
		int time=0;
		
		Queue<int[]>qu = new LinkedList<int[]>();
		Queue<int[]>removeCh = new LinkedList<int[]>();
		
		while(chCnt!=0) {
			time++;
			//bfs돌며 제거할 치즈 탐색
			int[][]isV = new int[n][m];
			qu.offer(new int[] {0,0});
			isV[0][0]=1;
			while(!qu.isEmpty()) {
				int[] ch = qu.poll();
				
				for (int i = 0; i < 4; i++) {
					int tx = ch[0]+dx[i], ty=ch[1]+dy[i];
					if(tx<0||tx>=n||ty<0||ty>=m)continue;
					
					//미방문 공기
					if(isV[tx][ty]==0 && map[tx][ty]==0) {
						isV[tx][ty]=1;
						qu.offer(new int[] {tx,ty});
					}
					//치즈 처음 만남
					else if(isV[tx][ty]==0) {
						isV[tx][ty]=1;
					}
					//치즈 2번째 만남
					else if(isV[tx][ty]==1 && map[tx][ty]==1) {
						isV[tx][ty]=2;
						removeCh.offer(new int[] {tx,ty});
					}
					
				}
			}
			
			//녹을 치즈 제거
			chCnt-=removeCh.size();
			while(!removeCh.isEmpty()) {
				int[] ch = removeCh.poll();
				map[ch[0]][ch[1]]=0;
			}
			
		}
		
		System.out.println(time);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 치킨집의 총 개수를 모르므로 arraylist로 관리

  - 살릴 치킨집의 개수는 알고 있으므로 배열로 관리

1. 가능한 모든 살릴수 있는 치킨집의 조합을 구한다 (combi 함수)

2. 각 조합에 대해, 치킨집 위치를 시작으로 bfs를 돌려 모든 집까지의 최소 거리를 구한다 (bfs함수)

3. bfs함수에서 구한 최소 거리가 더 작다면 min을 갱신

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

	static boolean[][]isV;//방문체크
	static int[][]map;
	static int[][]select;//살릴 치킨집
	static List<int[]>chicken;//모든 치킨집
	static int ans,n,m;
	static Queue<int[]> qu;
    
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
		
		map = new int[n+2][n+2];
		chicken = new ArrayList<>();
		//-1 패딩
		for (int i = 0; i < n+2; i++) {
			map[i][0]=-1;map[i][n+1]=-1;
			map[0][i]=-1;map[n+1][i]=-1;
		}
		
		//입력받기 + 치킨집 저장
		for (int i = 1; i <= n; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				map[i][j]=pint(st.nextToken());
				if(map[i][j]==2)chicken.add(new int[] {i,j});
			}
		}
		
		ans=Integer.MAX_VALUE;
		select=new int[m][2];
		combi(0, 0);
		System.out.println(ans);
        
	}
    
	static void combi(int cnt, int prev) {
		if(cnt==m) {
			qu = new LinkedList<int[]>();
			for (int i = 0; i < m; i++) {
				qu.offer(new int[] {select[i][0], select[i][1], 0});
			}
			ans = Math.min(ans, bfs());
			return;
		}
		
		for (int i = prev, len = chicken.size(); i < len; i++) {
			select[cnt][0]=chicken.get(i)[0];
			select[cnt][1]=chicken.get(i)[1];
			combi(cnt+1, i+1);
		}
	}
	
	static int bfs() {
		isV = new boolean[n+2][n+2];
		int dist=0;
		while(!qu.isEmpty()) {
			int[] cur = qu.poll();
			
			if(map[cur[0]][cur[1]]==1) {
				dist+=cur[2];
			}
			
			if(!isV[cur[0]+1][cur[1]] && map[cur[0]+1][cur[1]]>=0) {
				isV[cur[0]+1][cur[1]]=true;
				qu.offer(new int[] {cur[0]+1, cur[1], cur[2]+1});
			}
			if(!isV[cur[0]-1][cur[1]] && map[cur[0]-1][cur[1]]>=0) {
				isV[cur[0]-1][cur[1]]=true;
				qu.offer(new int[] {cur[0]-1, cur[1], cur[2]+1});
			}
			if(!isV[cur[0]][cur[1]+1] && map[cur[0]][cur[1]+1]>=0) {
				isV[cur[0]][cur[1]+1]=true;
				qu.offer(new int[] {cur[0], cur[1]+1, cur[2]+1});
			}
			if(!isV[cur[0]][cur[1]-1] && map[cur[0]][cur[1]-1]>=0) {
				isV[cur[0]][cur[1]-1]=true;
				qu.offer(new int[] {cur[0], cur[1]-1, cur[2]+1});
			}
			
		}
		
		return dist;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 폭탄 진행현황을 index로 검사한다

1. 현재 index에 맞는 문자가 들어오면 : 누적 후 index+1

2. 현재 index와 다른 문자가 들어오면

  - 폭탄의 첫 문자이다 : 새 폭탄의 시작점일 가능성, 현재 index정보를 백업하고 누적, index=1부터 다시 시작

  - 일반 문자이다 : 폭탄이 아니므로 모든 index를 제거, 누적된 문자들을 출력 문자열에 추가하고 index=0

  - 폭탄의 마지막 문자이다 : 폭탄이 터진다. 누적한 문자를 제거하고 백업한 index복구, 없으면 index=0

3. 모든 문자를 순회 후 : 누적한 문자가 있다면 출력 문자열에 추가

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringBuilder sb2;
		
		String s = br.readLine();
		String boom = br.readLine();
		
		int idx=0;
		Stack<Character> charStack = new Stack<>();
		Stack<Integer> idxStack = new Stack<>();
		
		for (int i = 0; i < s.length(); i++) {
			char cur = s.charAt(i);
			
			if(cur==boom.charAt(idx)) {
				//폭탄이 순조롭게 진행중
				idx++;
				charStack.add(cur);
				if(idx == boom.length()) {
					//폭탄의 완성
					//charStack에서 완성한 boom 비우기
					
					for (int j = 0; j < idx; j++) {
						charStack.pop();
					}
					//idx가 존재한다면, 복구하기
					if(!idxStack.isEmpty()) {
						idx = idxStack.pop();
					}else {
						idx = 0;
					}
				}
			}
			else {
				if(cur==boom.charAt(0)) {
					//새 폭탄의 시작
					idxStack.add(idx);
					charStack.add(cur);
					idx=1;
				}
				else {
					//평범한 문자열일 경우
					//쌓은 idx 다비우고
					idxStack.clear();
					
					//쌓인 char들은 boom이 아니므로 다 넣는다
					sb2 = new StringBuilder();
					while(!charStack.isEmpty()) {
						sb2.append(charStack.pop());
					}sb.append(sb2.reverse());
					//마지막에 현재 문자 반영
					sb.append(cur);
					idx=0;
				}
			}
		}
		sb2 = new StringBuilder();
		while(!charStack.isEmpty()) {
			sb2.append(charStack.pop());
		}sb.append(sb2.reverse());
		if("".equals(sb.toString())) System.out.println("FRULA");
		else System.out.println(sb);
        
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

* 요약하자면 y번째 자리에 x번 수가 있을때

  - y자릿수를 만드는데 필요한 index를 x번 가산 ( 1 ~ y-1 자리에 등장하는 수 처리 )

  - 앞에서 등장한 prev 숫자들을 x*y번 가산 ( y+1 ~ 자리에 등장하는 수 처리 )

  - x보다 작은 수들을 y자릿수씩 가산 ( y 자리에 등장하는 수 처리 )

  - 3부분으로 나눠 처리하는 방법이다

0. 10단위로, 그 아랫 페이지까지 나오는 0~9의 갯수를 미리 계산해 저장한다

  - 1000페이지 미만까지 나오는 숫자는, 100페이지 미만에서 나오는 숫자들이 10회 반복해서 나오고

    + 1~9(앞자리)가 각 100번씩 나온다

  - 계산의 편의를 위해 0 또한 앞자리로 존재한다고 가정하고 연산, 마지막에 제거한다

1. 앞에서부터 숫자와 자릿수를 추출한다 ( cur, len )

2. len에 해당하는 index의 값을, cur번 더해준다 ( 

  - ex) 543에서 5를 처리할 때 : 5와 3(100의 자릿수)을 추출, index의 3번째(100까지 나오는 숫자) 배열을 5회 가산

3. prev배열은 앞에서 등장한 숫자 정보를 가지고 있으며, 현재 자리에서 반복하는 횟수만큼 가산된다

  - ex) 543에서 4를 처리할 때 : 5는 40회 가산되어야한다

4. 현재 cur에 대해, 0~cur-1까지의 숫자는 자릿수만큼 등장하므로, 가산해준다

  - ex) 543에서 4를 처리할 때, 0,1,2,3은 10번씩 등장할 것이다

5. 마지막 자리를 처리할때는, prev배열을 1회 추가로 가산해야 한다

  - 543에서 4를 처리할 때는 prev배열을 50X, 51X, 52X, 53X에 대해 4 * 10회 가산해주고,

  - 54X에 대한 처리는 X가 불확실하므로 아래 자릿수에서 하게 된다

  - 하지만 마지막 자릿수인 3에선 불확실한 수가 없으므로 540, 541, 542, 543 총 4 * 1회 해주게 된다

6. 맨 앞에 등장한 0을 제거한다.

  - 가장 앞의 0은 1의 자릿수에선 1번, 10의 자릿수에선 10번, 100의 자릿수에선 100번 등장한다.

  - ex) 543은 100의 자릿수이므로, 총 111번의 0이 등장한다

  - 주어진 수의 자릿수까지 1, 10, 100을 계속 빼준다

7. 나중에 다시 보기위해 작성한 설명인데, 미래의 내가 이걸 알아들을지 자신이 없다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long[]page = new long[10];
		long[]prev = new long[10];
		long[]ans = new long[10];
		
		ArrayList<long[]>index=new ArrayList<>();
		index.add(page.clone());
		int cnt=1;
		//전처리
		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				page[j]*=10;
				page[j]+=cnt;
			}
			index.add(page.clone());
			cnt*=10;
		}

		String N = br.readLine();
		int len = N.length();
		
		//0번 자리부터
		for (int i = 0; i < N.length(); i++, len--) {
			int cur = N.charAt(i)-'0';

			long[] curIdx = index.get(len-1);
			long repeat = (long)Math.pow(10, len-1);
			for (int j = 0; j <= 9; j++) {
				ans[j]+=curIdx[j]*cur;
				ans[j]+=prev[j]*repeat*cur;//prev처리
			}
			
			//가장 앞자리 처리
			for (int j = 0; j < cur; j++) {
				ans[j]+=repeat;
			}
			
			prev[cur]++;
		}
		for (int j = 0; j <= 9; j++) ans[j]+=prev[j]; // prev배열 추가 1회 처리
		for (int i = 0; i < N.length(); i++) ans[0]-=Math.pow(10, i); // 맨 앞에 등장한 0 처리
		for (int i = 0; i <= 9; i++) System.out.print(ans[i]+" ");
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. reverseRow : 행을 뒤집고, rowSum/colSum을 갱신하는 함수

  - reverseCol : 열을 뒤집고, rowSum/colSum을 갱신하는 함수

  - toOrigin : 뒤집었던 열(t2변수에 bitmask로 저장됨)들을 복구하는 함수 

  - findmin : 부분집합을 만들고, 열을 뒤집고, 행을 검사하는 함수

1. 배열의 모든 행에 대해, 모든 가능한 부분집합을 만들어 reverse한다

2. 1번의 모든 경우에 대해, 값이 음수인 모든 열을 뒤집어본다

  - 값이 0인 열이 있다면 뒤집어도 0이므로, 양수가 될수 없으니 즉시 원상복귀 후 return한다

3. 2번을 통해 모든 열이 양수가 된 후에도 모든 행이 양수를 유지하고 있다면, 옳은 P배열이다

  - min값 갱신

4. min의 최댓값은 (N+M)/2이므로, (N+M)/2+1을 초깃값으로 정한다

  - ( N, M은 18 이하이므로 19 이상의 임의의 수를 사용해도 문제 없다 )

  - 동일한 값을 유지한다면 P배열을 만드는게 불가능했단 의미로, -1을 출력한다

  - 만드는게 가능했다면 구한 min값을 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

		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];
		rowSum = new int[N];
		colSum = new int[M];
		min=(N+M)/2+1;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				colSum[j]+=map[i][j];
				rowSum[i]+=map[i][j];
			}
		}
		findmin(0, 0);
		
		if(min==(N+M)/2+1)System.out.println(-1);
		else System.out.println(min);
		
	}
	static int[] rowSum;//행 합계
	static int[] colSum;//열 합계
	static int[][]map;
	static int N,M,min;
	
	static void findmin(int cnt, int colChk) {
		if(cnt==M) {
			//행을 뒤집은 부분집합 완성
			int temp=0, temp2=0;
			for (int i = 0; i < N; i++) {
				if(rowSum[i]==0) {
					toOrigin(temp2);
					return;
				}
				else if(rowSum[i]<0) {
					reverserow(i);
					temp++;
					temp2 = temp2|1<<i;
				}
			}
			for (int i = 0; i < M; i++) {
				if(colSum[i]<=0) {
					toOrigin(temp2);
					return;
				}
			}
			min=min<colChk+temp?min:colChk+temp;
			toOrigin(temp2);
			
			return;
		}
		
		//안선택
		findmin(cnt+1,colChk);
		//선택
		reversecol(cnt);
		findmin(cnt+1,colChk+1);
		reversecol(cnt);
		
		
	}
	static void toOrigin(int t2) {
		for (int i = 0; i < N; i++)if((t2&1<<i)!=0)reverserow(i);
	}
	
	static void reverserow(int idx) {
		for (int i = 0; i < M; i++) {
			map[idx][i] =-map[idx][i];
			colSum[i] = colSum[i] +map[idx][i]*2; 
		}
		rowSum[idx]*=-1;
	}
	static void reversecol(int idx) {
		for (int i = 0; i < N; i++) {
			map[i][idx]=-map[i][idx];
			rowSum[i] = rowSum[i] +map[i][idx]*2; 
		}
		colSum[idx]*=-1;
	}
	
	
}

[문제링크]

0. 모든 가방 무게에 대해, n-1번째 물건을 고려한 최적의 선택이 존재한다고 하면,

n번째 물건의 무게가 w, 가치가 v일때 무게 j짜리 가방의 최적해는

  - n번째 물건을 선택하지 않는 경우 ( n-1번의 무게 j짜리 최적해 )

  - n번째 물건을 선택한 경우 ( v + n-1번의 무게 j-w짜리 최적해 )

둘 중 큰 경우이다

1. 가상의 무게 0, 가치 0인 물건을 가정한다. ( 첫번째 연산에서 '이전 결과값'의 역할을 한다)

2. 첫번째 물건부터 차례대로, 가능한 모든 무게에 대해 넣는 경우와 넣지 않는 경우를 비교해 둘 중 큰 값을 선택한다

3. n번째 물건까지 종료한 최종 값이 최적해가 된다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[][]item = new int[n][2];
		for (int i = 0; i < n; i++) {
			st=new StringTokenizer(br.readLine()," ");
			item[i][0]=pint(st.nextToken());
			item[i][1]=pint(st.nextToken());
		}
        //첫번째 행 / 열의 0 값은 dp 연산에서 사용한다
        int[][]dp = new int[n+1][m+1];
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(j>=item[i-1][0]) {
                	//넣을 수 있다면 넣는 경우와 안넣는 경우를 비교한다
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-item[i-1][0]]+ item[i-1][1]);
				}
				else {
                	//넣지 못한다면 이전 결과 유지
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		
		System.out.println(dp[n][m]);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 1번 노드에서 v1,v2를 거쳐 N번 노드로 이동하는 방법은 2가지이다

  - v1을 먼저 방문 : 1-v1-v2-N

  - v2를 먼저 방문 : 1-v2-v1-N

  - 조건상 두 지점간 거리의 최댓값은 800개의 노드 가 1000 길이의 길로 연결됬을 경우인 799K이다

1. 1번노드, v1번 노드, v2번 노드에서 각각 다익스트라를 돌려, 다른 노드로 가는 최솟값을 찾는다

2. 다익스트라 계산 후 1-v1-v2-N 과 1-v2-v1-N 두 방법 중 cost가 작은것을 찾는다

3. 이론상 최대치가 약 80만이므로, 1-v1 / v1-v2 / v2-N 3번의 이동이 다 최대 cost에 가깝다고 해도 총 cost는 240만보다 작다

  - cost가 300만 이상의 결과가 나왔다면 경로가 존재하지 않아 초깃값이 계산된 경우이므로 -1을 출력한다

  - 그 외라면 구한 cost를 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());

		int[][]graph = new int[n+1][n+1];
		
		for (int i = 0; i < m; i++) {
			st=new StringTokenizer(br.readLine()," ");
			int n1 = pint(st.nextToken());
			int n2 = pint(st.nextToken());
			int c = pint(st.nextToken());
			graph[n1][n2]=c;
			graph[n2][n1]=c;
		}
		st=new StringTokenizer(br.readLine()," ");
		int n1 = pint(st.nextToken());
		int n2 = pint(st.nextToken());
	
		//다익스트라 준비물 * 3
		int[]dilk1=new int[n+1];
		int[]dilkn1=new int[n+1];
		int[]dilkn2=new int[n+1];
		Arrays.fill(dilk1, 3000000);
		Arrays.fill(dilkn1, 3000000);
		Arrays.fill(dilkn2, 3000000);
		
		boolean[] isV=new boolean[n+1];
		boolean[] isVn1=new boolean[n+1];
		boolean[] isVn2=new boolean[n+1];
		dilk1[1]=0;
		dilkn1[n1]=0;
		dilkn2[n2]=0;
		
		for (int i = 0; i < n; i++) {
			//아직 방문 안한 노드 중 가장 가까운 노드 탐색
			int min=Integer.MAX_VALUE, minnode=0;
			int minn1=Integer.MAX_VALUE, minnoden1=0;
			int minn2=Integer.MAX_VALUE, minnoden2=0;
			for (int j = 1; j <= n; j++) {
				if(!isV[j] && dilk1[j]<min) {
					min=dilk1[j];
					minnode=j;
				}if(!isVn1[j] && dilkn1[j]<minn1) {
					minn1=dilkn1[j];
					minnoden1=j;
				}if(!isVn2[j] && dilkn2[j]<minn2) {
					minn2=dilkn2[j];
					minnoden2=j;
				}
			}
			//해당 노드 방문처리
			isV[minnode]=true;
			isVn1[minnoden1]=true;
			isVn2[minnoden2]=true;
			
			for (int j = 1; j <= n; j++) {
				//아직 방문 안한 노드에 대해 cost 업데이트
				if(!isV[j] && graph[minnode][j]!=0) {
					dilk1[j]=Math.min(dilk1[j], dilk1[minnode]+graph[minnode][j]);
				}
				if(!isVn1[j] && graph[minnoden1][j]!=0) {
					dilkn1[j]=Math.min(dilkn1[j], dilkn1[minnoden1]+graph[minnoden1][j]);
				}
				if(!isVn2[j] && graph[minnoden2][j]!=0) {
					dilkn2[j]=Math.min(dilkn2[j], dilkn2[minnoden2]+graph[minnoden2][j]);
				}
			}
			
		}
		
		//1->n1->n2->n
		int cost=3000000;
		
		cost = Math.min(dilk1[n1]+dilkn1[n2]+dilkn2[n], dilk1[n2]+dilkn2[n1]+dilkn1[n]);
		if(cost>=3000000)System.out.println(-1);
		else System.out.println(cost);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}