너비 우선 탐색, 그래프 이론, 그래프 탐색

2024년 9월 10일 01:04:44

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

나의 답

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 N, M;
	static char[][] map;
	static int[][][] visited;

	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 char[N][M];
		for (int r = 0; r < N; r++) {
			map[r] = br.readLine().toCharArray();
		}
		min = N * M + 1;

		visited = new int[N][M][2];
		
		System.out.println(bfs(0, 0));
	}

	static int min;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static int bfs(int r, int c) {
		Queue<int[]> q = new LinkedList<>();
		// r좌표, c좌표, 이동거리, 벽 부순 여부
		q.add(new int[] { 0, 0, 1, 0 });
		// 방문체크
		visited[0][0][0] = 1;

		while (!q.isEmpty()) {
			// 큐에서 뽑기
			int[] curr = q.poll();
			// 종점 도착 시 종료
			if (curr[0] == N - 1 && curr[1] == M - 1)
				return curr[2];
			// 상하좌우 탐색
			for (int i = 0; i < 4; i++) {
				int nr = curr[0] + dr[i];
				int nc = curr[1] + dc[i];
				// 범위 벗어나으면 패스
				if (0 > nr || N <= nr || 0 > nc || M <= nc)
					continue;
				// (1) 벽일 때 기회 남아있으면 기회 차감하고 큐에 삽입 / 기회 없으면 패스
				if (map[nr][nc] == '1') {
					if (curr[3]==0 && visited[nr][nc][1] == 0) {
						visited[nr][nc][1] = curr[2] + 1;
						q.add(new int[] { nr, nc, curr[2] + 1 , 1});
					}
				}
				// (2) 0이면 그냥 큐에 삽입
				else {
					if (visited[nr][nc][curr[3]] == 0) {
						visited[nr][nc][curr[3]] = curr[2] + 1;
						q.add(new int[] { nr, nc, curr[2] + 1, curr[3]});
					}
				}
			}
		}
		return -1;
	}
}

프림 알고리즘

• 최소신장트리를 찾는 그리디 알고리즘
  
  
• 그래프의 모든 정점을 최소 비용으로 연결하는 트리
  
  
• 간선 중심의 크루스칼 알고리즘과 다르게, 정점 중심적 접근 방식임
  
  
• 도로망 설계나 네트워크 설계, 통신 네트워크 설계, 전력망 설계 등의 문제에 주로 활용될 수 있음

동작 원리

1. 임의의 정점에서 시작해 최소 비용인 간선을 선택(연결)

2. 선택한 간선의 끝에 있는 정점을 방문 체크하고, 그 정점에서 나가는 간선 중 가장 작은 간선을 선택

3. 같은 방법으로 모든 정점이 연결될 때까지 반복

장점

• 정점 중심의 알고리즘으로, 간선이 많은 그래프에 유리함

단점

• 간선의 수가 적을 경우 타 알고리즘에 비해 효율이 떨어질 수 있음
  
  
• 가중치를 저장하고 관리하는 과정에서 추가적인 메모리가 필요할 수 있음

구현

1. 방문체크배열(visited), 인접배열(adjArr), 시작점으로부터의 거리(dist)를 저장할 배열이 필요

2. dist배열을 모두 무한대로 설정하고, 시작점만 0으로 변경

3. dist배열에서 최소값을 가지면서, 아직 방문하지 않은 정점을 탐색 정점으로 선택 & 방문 체크

4. 인접배열을 통해 탐색하고자 하는 정점에서 출발하는 모든 간선 중 가장 낮은 간선을 선택하고, dist배열에 가중치 기록

5. dist 배열에서 최소값을 가지면서 아직 방문하지 않은 정점이 바로 다음 정점임

import java.util.Arrays;
import java.util.Scanner;

public class Prim {
	
	static final int INF = Integer.MAX_VALUE;
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt(); //정점의 번호 0번부터 시작
		int E = sc.nextInt(); //간선의 수
		
		//인접행렬 방식으로 
		int[][] adjArr = new int[V][V];
		
		for(int i = 0 ; i<E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int W =sc.nextInt();
			
			adjArr[A][B]=adjArr[B][A] = W; //무향
		} //입력 끝
		
		//방문체크 배열
		boolean[] visited = new boolean[V]; //해당 정점 선택
		int[] dist = new int[V]; // 선택한 간선의 가중치
		
		// dist 배열 무한대로 초기화
		for(int i = 0 ; i<V ; i++) {
			dist[i] = INF;
		}
		
		//시작 정점 선택
		dist[0] = 0; 
		int ans = 0;
		//가중치 배열을 돌면서 가장 값이 낮은것을 선택
		for(int i = 0 ; i<V; i++) { //V번 돌아도 괜찮아~
			int min = INF;
			int idx = -1;
			//가장 작으면서 아직 방문하지 않은 정점 선택
			for(int j = 0; j<V; j++) {
				if(!visited[j] && dist[j] < min) {
					min = dist[j];
					idx = j;
				}
			}
			visited[idx] = true; //방문체크
			ans += dist[idx];
			//방문하지 않았고 갱신할 수 있으면 갱신해 (idx)
			for(int j = 0 ; j<V; j++) {
				if(!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
					dist[j] = adjArr[idx][j];
				}
			}
		}
		
		System.out.println(ans);
		
		
		
		
		
		
		
		
		
	}
	
	
	
	
}

크루스칼 알고리즘

• 최소신장트리(MST)를 찾는 가장 대표적 방법이다
• 그래프의 모든 정점을 연결할 때, 가장 적은 비용으로 연결할 때 사용하는 알고리즘
• makeSet, findSet, union 메서드가 사용됨

동작 원리

1. 모든 간선을 가중치에따라 오름차순 정렬함

2. 가중치가 낮은 간선부터 선택하여 사이클이 형성되지 않을 경우 간선을 최종 채택

3. 간선을 추가할 땐 상호 배타 집합(Union-find)자료구조를 사용해 사이클 확인하고,
    같은 집합이 아니면 합집합으로 간선 연결 처리.

4. 같은 방법으로 모든 정점이 연결될 때까지 반복

활용 사례

1. 네트워크 설계 : 인터넷, 전기 등의 연결망 구성 시 연결 비용을 최소화하는 문제에 사용

2. 도로망 설계 : 여러 도시를 연결하는 도로망을 설계할 때 최소 비용으로 도시를 연결하기 위해 사용

장점

• 간선을 선택해나가는 방식으로 구현이 간단한 편이다.
  
  
• 간선을 정렬하는 방식이기 때문에, 간선의 수가 적은 경우에 유리하다.

단점

• 간선을 정렬해야 한다는 점이 시간복잡도를 증가시킬 수 있음
  
  
• 간선이 많을 때 비효율적일 수 있음

구현

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Kruskal {
	// 간선들을 객체화하여 배열로 관리하기 위한 간선 클래스 정의
	static class Edge implements Comparable<Edge> {
		int A, B, W;

		public Edge(int a, int b, int w) {
			super();
			A = a;
			B = b;
			W = w;
		}
		// 가중치를 기준으로 오름차순
		@Override
		public int compareTo(Edge o) {
			return this.W - o.W;
		}
	}

	static int[] p; // 대표자를 저장할 배열

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

		int V = sc.nextInt(); // 정점의 개수(정점의 시작번호를 보고)
		int E = sc.nextInt(); // 간선의 개수

		Edge[] edges = new Edge[E];

		for (int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B= sc.nextInt();
			int W = sc.nextInt();
			edges[i] =new Edge(A,B,W);

			edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
		} // 입력 끝

		// 간선을 오름차순 정렬
		Arrays.sort(edges);

		// 상호배타집합 (서로소집합, 유니온파인드)
		p = new int[V];

		// 자기 자신을 부모로 만들어 부모노드를 저장하는 배열에 저장
		for (int i = 0; i < V; i++) {
			p[i] = i;
		}
		
		int ans = 0; // 최소비용을 저장하기 위한 변수
		int pick = 0; // 채택한 간선의 개수

		for (int i = 0; i < E; i++) {
			// 사이클 확인
			int px = findSet(edges[i].A);
			int py = findSet(edges[i].B);
			// 부모 노드가 서로 다르면 다른 집합이므로 간선 선택
			if (px != py) {
				union(px, py);
				ans += edges[i].W;
				pick++;
			}

			if (pick == (V - 1))
				break;

		}

		System.out.println(ans);

	}// main

	static int findSet(int x) {
		// 경로 압축 방식
		if (x != p[x])
			p[x] = findSet(p[x]);
		return p[x];
	}

	static void union(int x, int y) {
		p[y] = x;
	}
}

상호 배타 집합 알고리즘

• Disjoint Set 알고리즘, 분리집합 알고리즘, Union-Find 알고리즘 이라고도 불림
• 그래프, 트리에서 많이 사용
• 동일한 집합에 속하는지 여부를 판단하고, 서로 다른 집합을 합치는 연산에 관한 알고리즘

상호 배타 집합의 주요 연산

1. Make-Set

새로운 집합을 생성하는 연산. 자기 자신을 부모로 설정하여 트리 형태로 관리

2. Find-Set

특정 요소가 속한 집합을 찾는 연산.
가장 최상단의 부모 노드를 찾아 반환하는 형태로 구현된다.
이를 통해 두 노드가 서로 같은 부모를 공유하면 같은 집합에 속한 것이고,
다른 부모를 가진다면 서로 다른 집합에 속한 것임을 알 수 있다.

3. Union

두 집합을 하나로 병합하는 연산.

BFS가 필요한 상황?

1. 그래프의 연결 여부 판단: 그래프 노드가 연결되어있는지 판단할 수 있다. 최소신장트리 알고리즘 등에서 사용된다.

2. 사이클 검사 : 무방향 그래프에서 사이클이 있는지 여부를 확인할 때 사용

장점

• 집합 관리에 효율적이다. 시간복잡도가 거의 상수 시간에 가까워진다.
  
  
• 크루스칼 알고리즘과 같은 최소 신장 트리 알고리즘에서 그래프의 연결성 관리하는 데 필수적이다.

단점

• 새로운 요소를 추가하는 연산이 없어 고정된 집합에서만 사용 가능
  
  
• 트리 구조로 관리하는 형태이기 때문에, 트리 높이를 효율적으로 유지하기 위한 추가적 연산 필요

구현

public class DisjointSetArray {

    // Make-Set: 각 원소가 자신을 부모로 갖는 새로운 집합을 생성
    public static void makeSet(int[] parent, int[] rank, int n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 자신이 부모
            rank[i] = 0;    // 초기 랭크는 0
        }
    }

    // Find-Set: x가 속한 집합의 루트(대표자)를 찾음, 경로 압축 적용
    public static int findSet(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = findSet(parent, parent[x]);  // 경로 압축
        }
        return parent[x];
    }

    // Union: 두 집합을 병합, 랭크를 기준으로 병합
    public static void union(int[] parent, int[] rank, int x, int y) {
        int rootX = findSet(parent, x);
        int rootY = findSet(parent, y);

        if (rootX != rootY) {
            // 랭크를 기준으로 작은 트리를 큰 트리 밑에 붙임
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;  // rootY를 rootX에 병합
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;  // rootX를 rootY에 병합
            } else {
                parent[rootY] = rootX;  // 둘의 랭크가 같을 때
                rank[rootX]++;          // rootX의 랭크 증가
            }
        }
    }

    public static void main(String[] args) {
        int n = 5; // 5개의 원소
        int[] parent = new int[n];  // 부모 배열
        int[] rank = new int[n];    // 랭크 배열

        // Make-Set: 5개의 원소 각각을 독립적인 집합으로 생성
        makeSet(parent, rank, n);

        // Union 연산: 1과 2를 병합, 3과 4를 병합, 2와 3을 병합
        union(parent, rank, 1, 2);
        union(parent, rank, 3, 4);
        union(parent, rank, 2, 3);

        // Find-Set 연산: 1과 4가 같은 집합에 속하는지 확인
        if (findSet(parent, 1) == findSet(parent, 4)) {
            System.out.println("1과 4는 같은 집합에 속합니다.");
        } else {
            System.out.println("1과 4는 다른 집합에 속합니다.");
        }

        // Find-Set 연산: 5는 어느 집합에 속하는지 확인
        System.out.println("5의 대표: " + findSet(parent, 4));
    }
}

너비우선탐색 (BFS)

• Breadth-First Search
• 그래프 or 트리의 한 노드에서 탐색 시작. 인접한 모든 노드를 먼저 탐색한 후 그 다음 인접 노드를 탐색하는 방식
• 한 레벨 씩 확장해가며 탐색하는 방식!

동작 원리

1. 시작 노드를 큐에 넣고, 해당 노드 방문 처리
   
   
2. (1) 큐에서 노드를 하나 꺼냄
   (2) 방문 처리
   (3) 꺼낸 노드의 인접 노드를 모두 큐에 추가함
   
   
3. 큐가 빌 때까지 반복
   
   

BFS가 필요한 상황?

1. 최단 경로 탐색 : 같은 level을 모두 방문한 후 다음 level로 이동하므로, 최단 경로를 확실하게 탐색할 수 있다.

2. 모든 노드 탐색 : 시작 노드가 속한 모든 그래프, 트리의 연결 여부를 확인할 수 있음

3. 웹 크롤링 : 특정 페이지에서 연결된 페이지를 모두 방문할 때

장점

• 최단 경로 보장
  
  
• 계층 구조 탐색에 적합

단점

• 메모리 사용이 DFS에 비해 크다.
  
  
• 모든 노드를 깊이에 관계 없이 탐색하므로, 깊이 있는 노드를 우선 탐색해야할 때에는 비효율적일 수 있다.

구현

큐를 이용한 구현

import java.util.*;

public class BFSQueue {
    // 큐를 이용한 BFS 알고리즘 구현
    public static void bfsQueue(Map<Integer, List<Integer>> graph, int startNode) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        // 시작 노드를 큐에 추가하고 방문 처리
        queue.add(startNode);
        visited.add(startNode);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();  // 큐에서 노드를 꺼냄
            System.out.print(node + " ");  // 방문한 노드를 출력
            
            // 인접한 모든 노드를 탐색
            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);  // 인접 노드를 큐에 추가
                    visited.add(neighbor);  // 방문 처리
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 4));
        graph.put(2, Arrays.asList(1, 5, 6));
        graph.put(3, Arrays.asList(1, 7, 8));
        graph.put(4, Arrays.asList(1, 9));
        graph.put(5, Arrays.asList(2));
        graph.put(6, Arrays.asList(2));
        graph.put(7, Arrays.asList(2, 10));
        graph.put(8, Arrays.asList(3));
        graph.put(9, Arrays.asList(4));
        graph.put(10, Arrays.asList(7));

        bfsQueue(graph, 1);  // 1번 노드에서 BFS 시작
    }
}

깊이우선탐색 (DFS)

• Depth-First Search
• 그래프 or 트리에서 한 노드 지정해 탐색을 시작, 인접한 노드를 탐색하고 더 깊은 단계로 들어가며 탐색을 이어나감
• 한 경로를 끝까지 탐색한 후 다음 경로로 넘어간다

동작 원리

1. 시작 노드에서 출발하여 가장 깊은 노드까지 탐색을 진행
   
   
2. 더이상 방문할 노드가 없으면, 한 단계 위로 돌아가서 탐색을 이어나감
   
   
3. 모든 노드를 방문할 때까지 반복!
   
   

DFS가 필요한 상황?

1. 경로 탐색 문제 : 미로 탐색 등의 문제에서 특정 경로를 탐색해야 하는 경우

2. 연결 요소 탐색 : 그래프에서 특정 노드를 탐색해야 할 때, 모든 노드를 탐색해야 할 때

3. 백트래킹 : 퍼즐이나 조합을 탐색할 때 백트래킹 알고리즘의 기반이 되는 방식!

4. 사이클 탐지 : 순환 그래프의 경우 사이클의 여부를 탐지할 때 사용 가능

장점

• 메모리 효율성 : BFS 방식에 비해 메모리 소비가 적다. 특히 그래프가 넓은 경우 더 효율적이다
• 깊이가 중요한 문제에 적합함.

단점

• 최적 경로가 보장되지 않는다. 최단 경로를 찾기 위해선 BFS가 적합
  
  
• 방문여부를 체크하지 않으면 무한 루프가 발생할 수 있다.

구현

1. 스택을 이용한 구현

import java.util.*;

public class DFSStack {
    // DFS 알고리즘을 스택을 이용해 구현한 코드
    public static void dfsStack(Map<Integer, List<Integer>> graph, int startNode) {
        Stack<Integer> stack = new Stack<>();
        Set<Integer> visited = new HashSet<>();
        
        // 시작 노드를 스택에 추가
        stack.push(startNode);
        
        while (!stack.isEmpty()) {
            int node = stack.pop();  // 스택에서 노드를 꺼냄
            
            if (!visited.contains(node)) {
                visited.add(node);  // 방문한 노드로 처리
                System.out.print(node + " ");  // 방문 순서 출력
                
                // 인접 노드를 스택에 추가
                for (int neighbor : graph.get(node)) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 7));
        graph.put(2, Arrays.asList(1));
        graph.put(3, Arrays.asList(1, 4, 6));
        graph.put(4, Arrays.asList(3));
        graph.put(5, Arrays.asList(5));
        graph.put(6, Arrays.asList(3));
        graph.put(7, Arrays.asList(1));
        graph.put(8, Arrays.asList(7));

        System.out.println("DFS using stack:");
        dfsStack(graph, 1);  // 0번 노드에서 DFS 시작
    }
}

2. 재귀를 이용한 구현

메서드 호출은 Java 자체에서 스택 방식으로 처리되므로, 이를 이용해 재귀함수를 만들어 구현하는 방법.

가장 많이 사용된다!

import java.util.*;

public class DFSStack {
    // 재귀를 이용한 DFS
    public static void dfsRecursive(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
        // 노드를 방문하고 출력
        visited.add(node);
        System.out.print(node + " ");
        
        // 인접 노드를 재귀적으로 방문
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, Arrays.asList(2, 3, 7));
        graph.put(2, Arrays.asList(1));
        graph.put(3, Arrays.asList(1, 4, 6));
        graph.put(4, Arrays.asList(3));
        graph.put(5, Arrays.asList(5));
        graph.put(6, Arrays.asList(3));
        graph.put(7, Arrays.asList(1));
        graph.put(8, Arrays.asList(7));

        System.out.println("DFS using stack:");
        dfsStack(graph, 1);  // 0번 노드에서 DFS 시작
    }
}

퀵정렬

• 분할정복 알고리즘의 일종!
• 시간복잡도 : O(NlogN)
• 피벗을 정한 후, 피벗을 기준으로 피벗보다 작은 쪽과 큰 쪽으로 분할하며 정렬하는 방식
• 최악의 경우는 이미 배열이 정렬되어 있거나 역순으로 되어있을 경우, O(n^2)의 시간복잡도 발생 가능

정렬 방식

1. 피벗을 선택 (맨 앞, 가운데 ,맨 끝, 랜덤 등...)
   
   
2. 피벗을 기준으로 피벗보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 정렬
   
   
3. 정렬이 완료되면 또다른 피벗을 정해 같은 방법으로 정렬
   
   

	static void quickSort(int left, int right) {
		if (left < right) {
			int pivot = left;
			int L = left + 1;
			int R = right;

			while (L <= R) {
				// pivot보다 큰놈 찾을 떄까지
				while (L <= R && arr[pivot] >= arr[L]) {
					L++;
				}
				// pibot보다 작은놈 찾을 때까지
				while (arr[pivot] < arr[R]) {
					R--;
				}

				// L, R 자리 바꾸기
				if (L < R) {
					int tmp = arr[L];
					arr[L] = arr[R];
					arr[R] = tmp;
				}
			}
			// R과 자리 바꾸기
			int tmp = arr[R];
			arr[R] = arr[pivot];
			arr[pivot] = tmp;

			pivot = R;
			quickSort(left, pivot - 1);
			quickSort(pivot + 1, right);
		}
	}

병합정렬

• 분할정복 알고리즘의 일종!
• 시간복잡도 : O(NlogN)
• 배열을 더이상 나눠지지 않을 때까지 반으로 나눈 후 각각을 정렬하여 병합하는 방식
• 별도의 배열을 생성하여 정렬한 요소들을 담아줘야 함
  => 정렬 과정에서 계속 정렬 상태가 유지되는 안정 정렬 방식

정렬 방식

1. 배열을 반으로 나눈다.  (분할)
   
   
2. 왼쪽 배열의 1번째 인덱스, 오른쪽 배열의 1번째 인덱스부터 비교 (정렬)
3. 작은 것을 우선으로 새로운 배열에 옮긴다. (병합)

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

            merge(array, left, mid, right);
        }
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int L = mid - left + 1;
        int R = right - mid;

        int[] leftArray = new int[L];
        int[] rightArray = new int[R];

        for (int i = 0; i < L; ++i) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < R; ++j) {
            rightArray[j] = array[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < L && j < R) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < L) {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < R) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] data = {12, 11, 13, 5, 6, 7};
        mergeSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}

[백준] 10158번 개미

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

문제

입력 :

첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다. 

출력 :

출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다. 

나의 답안

 1번째 시도 (실패)

개미가 (p, q) 좌표에서 시작, 초기엔 시간마다 (+1, +1) 씩 이동하다가

x한계선에 부딪히면 (-1, +1)이동,  

y한계선에 부딪히면 (+1, -1) 이동,

x, y 한계선에 부딪히면 (-1, -1) 이동하도록 설계했다.

이동할 때마다 이동할 위치를 미리 확인하여 한계선 여부를 확인하고,
확인된 한계선의 좌표 이동값만 -1을 곱하여 바꿔주도록 했다.

<1차 시도(실패 코드)>

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

public class Main {

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

		// 상하좌우 확인용 배열
//		int[] dr = { -1, 1, 0, 0 };
//		int[] dc = { 0, 0, -1, 1 };
		// 시간당 이동량
		int[] move = { 1, 1 };
		// 개미 현재위치 변수
		int r, c;
		// 개미가 이동할 위치 변수
		int nr, nc;
		// 좌표상으로 개미의 이동 가능 범위가 x : 0 ~ w, y : 0 ~ h 이므로
		// => 배열로는 w+1행 h+1열 지도 생성해야 함
		int w = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		// 개미 위치 입력받음
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		// 시간 입력
		int time = Integer.parseInt(br.readLine());

		for (int t = 1; t <= time; t++) {
			// 사방 탐색
			nr = r + move[0];
			nc = c + move[1];
			// nr값이 범위를 넘으면 => 이동량 (-1, 1)
			if (nr < 0 || nr > w) move[0] *= -1;
			// nc값이 범위를 넘으면 => 이동량 (1, -1)
			if (nc < 0 || nc > h) move[1] *= -1;
			// 개미 이동
			r += move[0];
			c += move[1];
		}

		// time시간 후 개미 위치 출력
		System.out.println(r + " " + c);
	}
}

2번째 시도 (성공)

1차 시도에서 시간 초과 발생. time이 최대 2억이므로 for문을 사용하면 안될 것이라고 판단했다.

1.  time을 최대 좌표값으로 나눴을 때 
   
   몫이 짝수이면 => 2바퀴 돌고 제자리로 돌아오고, 이동량은 그대로 +1
   
   몫이 홀수이면 => 1바퀴 돌아 원래 자리의 대칭점으로 이동. 이동량은 반대인 -1
   
   
2. time을 좌표값으로 나눈 나머지만큼 이동해주면 최종 위치값이 된다.

<2차 코드(성공)>

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

public class S3_10158_개미 {

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

		// 개미 현재위치 변수
		int r, c;
        
		st = new StringTokenizer(br.readLine());
        
		// 개미 위치 입력받음
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
        
		// 시간 입력
		int time = Integer.parseInt(br.readLine());
        
		// 몫이 짝수이면 다시 제자리로 돌아온 것과 같음
		if (time / w % 2 == 0) {
			// 제자리에서 (+1 * 나머지) 만큼 이동
			r = r + (time % w) > w ? w - (r + (time % w) - w) : r + (time % w);
		// 몫이 홀수이면 원래 자리의 대칭점으로 이동한 것과 같음
		} else {
			// 대칭점에서 (-1 * 나머지) 만큼 이동
			r = r + (time % w - w) < 0 ? - (r + (time % w - w)) : r + (time % w - w);
		}
        
		// y좌표도 동일하게 이동 처리
		if (time / h % 2 == 0) {
			c = c + (time % h) > h ? h - (c + (time % h) - h) : c + (time % h);
		} else {
			c = c + (time % h - h) < 0 ? - (c + (time % h - h)) : c + (time % h - h);
		}
        
		System.out.println(r + " " + c);
	}
}

개선 사항

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] size = br.readLine().split(" ");
        int w = Integer.parseInt(size[0]);
        int h = Integer.parseInt(size[1]);
        
        String[] point = br.readLine().split(" ");
        int p = Integer.parseInt(point[0]);
        int q = Integer.parseInt(point[1]);
        
        int t = Integer.parseInt(br.readLine());
        
        int x = (t + p) % (2 * w);
        int y = (t + q) % (2 * h);
        
        if (x > w) {
            x = 2 * w - x;
        }
        
        if (y > h) {
            y = 2 * h - y;
        }
        
        System.out.println(x + " " + y);
    }
    
}

• x, y좌표의 계산을 매우 간결하게 처리했다.
• x, y좌표가 범위를 넘었을 경우를 별도 if문으로 처리하여 가독성이 좋아졌다.

문제에 좌표가 있으면 일단 무조건 배열을 생성하고

시간별로 일일이 처리하도록 계산했었는데,

이렇게 간단한 계산식으로 처리할 수가 있다는 것을

바로 생각해내지 못했다.

항상 정해진 답은 없다는 것을 생각하고

더 효율적인 방법이 있을지 생각해봐야 하겠다.

병합정렬

• 분할정복 알고리즘의 일종!
• 시간복잡도 : O(NlogN)
• 배열을 더이상 나눠지지 않을 때까지 반으로 나눈 후 각각을 정렬하여 병합하는 방식
• 별도의 배열을 생성하여 정렬한 요소들을 담아줘야 함
  => 정렬 과정에서 계속 정렬 상태가 유지되는 안정 정렬 방식

정렬 방식

1. 배열을 반으로 나눈다.  (분할)
   
   
2. 왼쪽 배열의 1번째 인덱스, 오른쪽 배열의 1번째 인덱스부터 비교 (정렬)
3. 작은 것을 우선으로 새로운 배열에 옮긴다. (병합)

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

            merge(array, left, mid, right);
        }
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int L = mid - left + 1;
        int R = right - mid;

        int[] leftArray = new int[L];
        int[] rightArray = new int[R];

        for (int i = 0; i < L; ++i) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < R; ++j) {
            rightArray[j] = array[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < L && j < R) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < L) {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < R) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] data = {12, 11, 13, 5, 6, 7};
        mergeSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}