easy blog

DFS로 시도했으나 오답이다 이유를 생각해보면, DFS는 한붓그리기 라고 생각하면 된다.

파이프를 최단거리로 지나가는 경우도 생각할 수 있지만, 빙 돌아가는 경우에는 Level에 대한 부분이 애매해져버린다.

다른 풀이를 보니 visited 배열을 잘 사용해서 풀이 하는 경우가 있는것 같으나  visited를 구성하는 것이 번거로워 bfs로 변경함 ( 문제를 많이 풀다 보면, 둘을 번갈아가며 구현하는데 큰 어렴은 없다.)

단순하게 풀이하려 노력했다.

각 파이프 모양에서 나올 수 있는 움직임을 2차원 배열인 dx,dy로 저장.

보통의 bfs에서는 다음 단계(nr,nc)로 이동하고 보통 끝나지만 파이프가 연결됐는지 확인하기 위해

이동한 좌표(nrnr,ncnc) 에서 원래의 파이프(nr,nc)로 돌아올 수 있는지 확인을 하고 Q에 넣어주면 된다.

다른 사람들은 타입별로 파이프를 매핑해서 풀었는데, 이 방법이 더 직관적이지 않나 하는 생각이 든다.

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


class Solution {

	static int N, M, R, C, L;
	static int[][] dx = { {}, { 1, -1, 0, 0 }, { 1, -1 }, { 0, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 } };
	static int[][] dy = { {}, { 0, 0, -1, 1 }, { 0, 0 }, { 1, -1 }, { 1, 0 }, { 1, 0 }, { 0, -1 }, { 0, -1 } };
	static int[][] map;
	static boolean[][] visited;
	static int answer;
	private static boolean DBG = false;

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


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			answer = 0;
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			visited = new boolean[N][M];
			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());
				}
			}

			//dfs(0, R, C);
			bfs();
			
			sb.append(String.format("#%d %d\n",test_case, answer));
			//System.out.println(answer);
		}
		
		System.out.println(sb);
	}

	private static void bfs() {
		Queue<int []> Q = new LinkedList<>();
		
		Q.offer(new int[]{R,C});
		
		int level = 0 ; 
		while(!Q.isEmpty()) {
			
			if( level ==L) {
				return;
			}
			
			
			int size = Q.size();
			for ( int t = 0 ; t < size ; t++) {
				int[] pos =Q.poll();
				int r= pos[0], c=pos[1];
				if (visited[r][c])
					continue;
				
				visited[r][c] = true;
				answer++;
				
				int now = map[r][c];
				for (int i = 0; i < dx[now].length; i++) {
					
					int nr = r + dx[now][i];
					int nc = c + dy[now][i];
										
					if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc]!=0&& !visited[nr][nc]) {
						int next = map[nr][nc];
						if(DBG)
						System.out.printf("from[%d %d]to[%d %d]next map : %d visited : %b\n",r,c, nr,nc,next,visited[nr][nc] );
						for (int j = 0; j < dx[next].length; j++) {						
							int nrnr = nr + dx[next][j];
							int ncnc = nc + dy[next][j];						
							if (nrnr >= 0 && nrnr < N && ncnc >= 0 && ncnc < M && 
									nrnr == r && ncnc == c) {
								if(DBG)
								System.out.printf("offer[%d %d]next : %d\n", nr,nc,next);
								Q.offer(new int[] {nr,nc});
							}

						}

					}
				}
				
				
			}
			
			level ++;
			if(DBG)
			System.out.println("level : "+level);
			
		}
		
		
	}

	private static void dfs(int level, int r, int c) {

		if (visited[r][c])
			return;
		
		visited[r][c] = true;
		if(DBG)
		System.out.printf("visited [%d %d] set true\n", r,c, visited[r][c]);
		answer++;
		if(DBG)
		System.out.printf("enter & count [%d %d] %d\n", r,c ,answer);

		if (level == L+1) {
			return;
		} else {
			int now = map[r][c];
			for (int i = 0; i < dx[now].length; i++) {
				
				int nr = r + dx[now][i];
				int nc = c + dy[now][i];
				
				
				if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc]!=0&& !visited[nr][nc]) {
					int next = map[nr][nc];
					if(DBG)
					System.out.printf("from[%d %d]to[%d %d]next map : %d visited : %b\n",r,c, nr,nc,next,visited[nr][nc] );
					for (int j = 0; j < dx[next].length; j++) {						
						int nrnr = nr + dx[next][j];
						int ncnc = nc + dy[next][j];						
						if (nrnr >= 0 && nrnr < N && ncnc >= 0 && ncnc < M && 
								nrnr == r && ncnc == c) {
							if(DBG)
							System.out.printf("dfs[%d %d]next : %d\n", nr,nc,next);
							dfs(level + 1, nr, nc);
						}

					}

				}
			}

		}

	}
}

순열 사이클 : https://www.acmicpc.net/problem/10451

인접행렬을 순회하며 자기 자신을 마주치기 전까지 돌면 된다.

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

public class Main {

	static int N, T;
	static int answer = 0;
	static ArrayList<Integer>[] adj;
	static boolean[] visited;
	private static boolean DBG = false;

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

		T = Integer.parseInt(br.readLine());
		for (int test_case = 0; test_case < T; test_case++) {
			N = Integer.parseInt(br.readLine());
			visited = new boolean[N + 1];
			adj = new ArrayList[N + 1];
			for (int i = 1; i <= N; i++) {
				adj[i] = new ArrayList<Integer>();
			}
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; i++) {
				adj[i].add(Integer.parseInt(st.nextToken()));
			}

			for (int i = 1; i <= N; i++) {
				if (!visited[i])
					check(0, i, adj[i].get(0));
			}

			System.out.println(answer);
			answer =0;
		}
	}

	private static void check(int index, int s, int v) {

		if (v == s) {
			answer++;
			return;
		}

		if (visited[v])
			return;
		visited[v] = true;

		check(index + 1, s, adj[v].get(0));

	}

}

이분 그래프 : https://www.acmicpc.net/problem/1707

https://toastfactory.tistory.com/115

https://kukekyakya.tistory.com/96

DFS 및 BFS풀이

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

import java.util.*;

public class Main {

	static int V, E, T;
	static boolean DBG = false;
	static String answer = "YES";
	static ArrayList<ArrayList<Integer>> graph;
	static int[] visited, team;
	static int RED = -1;
	static int GREEN = 1;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			answer = "YES";
			found = false;
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			visited = new int[V];
			team = new int[V];
			graph = new ArrayList<ArrayList<Integer>>();

			for (int i = 0; i < V; i++) {
				graph.add(new ArrayList<Integer>());
			}

			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken()) - 1;
				int v2 = Integer.parseInt(st.nextToken()) - 1;
				graph.get(v1).add(v2);
				graph.get(v2).add(v1);
			}

			if (DBG) {
				int i = 0;
				for (ArrayList<Integer> arr : graph) {
					System.out.print("i : [" + i + "] ");
					i++;
					for (int v : arr) {
						System.out.print(v + " ");
					}
					System.out.println();
				}

			}

			for (int i = 0; i < V; i++) {
				if (visited[i] == 0) {
					dfs(0, i, 1);
					if (found)
						break;
				}
			}

			/*
			 * for (int i = 0; i < V; i++) if (team[i] == 0) { if (!bfs(i)) break; }
			 */

			System.out.println(answer);
		}

	}

	static boolean found = false;

	private static void dfs(int level, int vex, int color) {

		if (visited[vex] != 0)
			return;
		visited[vex]=1;
		team[vex] = color;

		for (int v : graph.get(vex)) {
			if (team[v] == team[vex]) {
				answer ="NO";
				found =true;
				return;
			}
			dfs(level + 1, v, color * -1);
		}

	}

	private static boolean bfs(int vex) {
		Queue<Integer> Q = new LinkedList<>();

		Q.offer(vex);
		team[vex] = RED;

		while (!Q.isEmpty()) {
			int now = Q.poll();
			for (int n : graph.get(now)) {
				if (team[now] == team[n]) {
					answer = "NO";
					return false;
				}
				if (team[n] == 0) {
					team[n] = team[now] * -1;
					Q.add(n);
				}

			}
		}
		return true;
	}

}