2295번: 세 수의 합

N(5 ≤ N ≤ 1,000) 개의 자연수로 이루어진 집합 U.

U에서 적당히 3개의 수를 뽑았을 때 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다.

이때 가장 큰 d를 찾아라

집합의 크기는 최대 1000이다. 집합이니 중복은 존재하지 않는다.

1000개에서 3개를 뽑고 전부 확인하면 시간초과가 발생할 것이다.

또한 집합 U의 원소는 2억보다 작거나 같은 자연수이다. 세 수를 더한 경우에도 정수 범위 내로 처리 가능하다.

두 수의 합으로 만들 수 있는 숫자들을 미리 기록해 놓고 빠르게 찾을 수 있으면 해결할 수 있다.

1. 두 수의 조합으로 만들 수 있는 합을 Set으로 관리
2. 입력받은 집합을 오름차순으로 정렬하고 뒤에서부터 확인
3. 현재 정답 후보와 후보 앞에 있는 숫자들을 빼가며 해당 값이 두 수의 합 Set에 존재하는지 확인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N;
    static List<Integer> nums;

    static void input() {
        N = scan.nextInt();
        nums = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            nums.add(scan.nextInt());
        }

        Collections.sort(nums);
    }

    static void solve() {
        Set<Integer> twoSum = new HashSet<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                twoSum.add(nums.get(i) + nums.get(j));
            }
        }

        for (int i = nums.size() - 1; i > 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                int cand = nums.get(i) - nums.get(j);
                if (twoSum.contains(cand)) {
                    System.out.println(nums.get(i));
                    return;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Plus One - LeetCode

단순하게 배열을 숫자로 변환하고 +1 한 다음 다시 배열로 변환하는 방식의 경우 배열의 최대 길이가 100이기에 long의 범위를 넘어선다.

따라서 배열의 값들이 0~9 사이 이기 때문에 carry를 통해 계산을 처리하는 방식으로 진행한다.

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        List<Integer> result = new ArrayList<>();
        int carry = 1;

        for (int i = n - 1; i >= 0; i--) {
            int num = digits[i];
            if (num + carry >= 10) {
                result.add(num + carry - 10);
            } else {
                result.add(num + carry);
                carry = 0;
            }            
        }

        if (carry != 0) {
            result.add(carry);
        }

        int[] answer = new int[result.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = result.get(answer.length - 1 - i);
        }

        return answer;
    }
}

House Robber - LeetCode

인접한 두 집을 털 수는 없다.

[1, 2, 3, 1]이라면 0번과 2번을 털면 4라는 최대 수익을 낼 수 있다.

즉 해당 위치의 집을 털거나 털지 않거나 둘 중 하나의 경우가 존재한다.

i위치에서의 최대는 i-1을 털었을 떄와 i-2를 털고 i를 털었을 때의 최대가 된다.

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }

        return dp[nums.length - 1];
    }
}

1655번: 가운데를 말해요

정수가 하나씩 주어졌을 때 지금까지 언급된 수 중에서 중간값을 말해야 한다.

1 → 1

5 → 1, 5 → 1

2 → 1, 5, 2 → 1, 2, 5 → 2

10 → 1, 2, 5, 10 → 2

-99 → 1, 2, 5, 10, -99 → -99, 1, 2, 5, 10 → 2

7 → -99, 1, 2, 5, 10, 7 → -99, 1, 2, 5, 7, 10 → 2

5 → -99, 1, 2, 5, 7, 10, 5 → -99, 1, 2, 5, 5, 7, 10 → 5

리스트에 숫자를 추가해 가며 정렬하고 중간값을 출력하면 된다.

그렇지만 숫자가 추가될 때마다 정렬하고 중간값을 찾으면 시간초과가 발생할 것이다.

중간이라는 의미는 중간 숫자보다 작은 것과 큰 것으로 나눌 수 있다.

1. 첫 입력이 mid값이다.
2. mid를 기준으로 두 그룹으로 나누기 위해 왼쪽 그룹 최대힙과 오른쪽 그룹 최소힙을 설정한다.
3. 다음 입력 값이 mid보다 작으면 왼쪽 그룹, 크다면 오른쪽 그룹으로 간다.
4. 두 그룹간의 크기 비교를 통해 중간값 변경 작업을 수행한다.

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

public class Main {

    static FastReader scan = new FastReader();
    static int N;

    public static void main(String[] args) {
        N = scan.nextInt();
        List<Integer> result = new ArrayList<>();
        int mid = scan.nextInt();
        result.add(mid);
        PriorityQueue<Integer> left = new PriorityQueue<>((a,b) -> Integer.compare(b, a)); // 최대
        PriorityQueue<Integer> right = new PriorityQueue<>();

        for (int i = 1; i < N; i++) {
            int num = scan.nextInt();
            if (mid < num) {
                right.add(num);
            } else {
                left.add(num);
            }

            if (right.size() - left.size() > 1) {
                left.add(mid);
                mid = right.poll();
            } else if (left.size() - right.size() >= 1) {
                right.add(mid);
                mid = left.poll();
            }
            result.add(mid);
        }

        for (int num : result) {
            System.out.println(num);
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

코딩테스트 연습 - 롤케이크 자르기 | 프로그래머스 스쿨 (programmers.co.kr)

조각마다 동일한 가짓수의 토핑이 올라가 있으면 공평하게 나누어진 것이다.

→ 토핑의 개수보다는 가짓수가 중요하다.

롤 케이크를 공평하게 자르는 방법의 수를 구하시오.

전체 토핑을 관리하며 포인트를 이동시켜 가며 확인을 한다.

1. 토핑 종류 : 개수 Map으로 기록
2. 포인터를 0부터 오른쪽으로 이동시켜한다.
3. 해당 포인터의 토핑을 Map 에서 1개 뺀다. 만약 개수가 0이 되면 제거한다.
4. 현재 내 토핑은 Set을 통해 관리한다.
5. 최종적으로 내 토핑 set과 전체 토핑 map의 크기가 같으면 공평한 것이다.

import java.util.*;

class Solution {
    public int solution(int[] topping) {
        Map<Integer, Integer> toppings = new HashMap<>();
        Set<Integer> myToppings = new HashSet<>();
        int answer = 0;
        
        for (int t : topping) {
            toppings.put(t, toppings.getOrDefault(t, 0) + 1);
        }
        
        for (int i = 0; i < topping.length; i++) {
            int t = topping[i];
            myToppings.add(t);
            toppings.put(t, toppings.get(t) - 1);
            if (toppings.get(t) == 0) {
                toppings.remove(t);
            }
            
            if (myToppings.size() == toppings.size()) {
                answer++;
            }
        }
        return answer;
    }
}

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 스쿨 (programmers.co.kr)

한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 한다.

예를 들어 ["119", "97674223", "1195524421"] 이 주어졌다면 “119”는 “1195524421”의 접두어가 됩니다.

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 그렇지 않다면 true

우선 접두어라는 것이 앞에 있다는 소리니 길이가 짧을 수밖에 없다. 주어진 배열을 길이로 정렬부터 하는 게 맞다는 생각이 든다.

트라이를 사용할까?

트라이를 구성하고 길이가 짧은 단어 부터 삽입해 간다.

삽입도중에 단어가 완성됐다는 플래그가 나오면 false를 반환하고 종료한다.

import java.util.*;

class Solution {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOf = false;
        
        public boolean isEndOf() {
            return isEndOf;
        }
        
        public void setEndOf(boolean end) {
            isEndOf = end;
        }
    }
    
    static class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public boolean insert(String word) {
            TrieNode current = root;
            for (char ch : word.toCharArray()) {
                current.children.putIfAbsent(ch, new TrieNode());
                current = current.children.get(ch);
                if (current.isEndOf()) {
                    // 삽입중인데 이미 단어가 완성된게 있다 -> 접두어 존재
                    return false;
                }
            }
            current.setEndOf(true);
            return true;
        }
    }
    
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book, (a, b) -> Integer.compare(a.length(), b.length()));
        Trie trie = new Trie();
        for (String number : phone_book) {
            if (!trie.insert(number)) {
                return false;
            }
        }
        
        return true;
    }
}

그런데 이 문제는 잘 생각해 보면 그럴 필요가 없다. 그냥 정렬해서 이전 것과 비교하면 된다. 문자열의 정렬은 사전순으로 이루어진다. 예를 들어 ["119", "97674223", "1195524421"] 이것의 정렬의 결과는 ["119", "1195524421", "97674223"] 이 된다. 따라서 접두어는 반드시 한 칸 앞에 존재한다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i = 1; i < phone_book.length; i++) {
            if (phone_book[i].startsWith(phone_book[i - 1])) {
                return false;
            }
        }
        return true;
    }
}

코딩테스트 연습 - 지형 이동 | 프로그래머스 스쿨 (programmers.co.kr)

각 칸에는 높이가 적혀있고 이동하려면 칸 사이 높이차가 height 이하여야 한다.

height보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있다.

사다리 설치 비용은 높이차만큼 들어간다.

최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하게 하라.

시작점 위치는 중요하지 않다. 어차피 모든 점을 도달하려면 어느 점에서 시작하던 상관없다.

현재 위치에서 이동 위치는 이동 가능한 지점과 이동 불가능한 지점으로 나누어진다.

이동 가능한 위치는 그냥 이동하면 된다. 이제 이동 불가능한 지점을 어떻게 다룰지 생각해야 한다.

현재 탐색 가능 범위를 탐색하면서 사다리를 설치해야 하는 위치와 비용을 저장한다.

그중 가장 적은 비용을 꺼내 사다리를 설치하고 그 지점부터 탐색을 다시 시작한다.

지속적으로 사다리 설치 후보를 추가해 가면서 모든 지점이 탐색될 때까지 탐색한다.

1. (0,0)부터 시작해서 탐색을 진행한다. 이 과정은 BFS를 통해 탐색을 한다.
2. 사다리를 설치해야 하는 지점이 있다면 PQ에 좌표와 비용을 추가한다.
3. 탐색 가능한 범위를 탐색한 후 모든 지점이 탐색되지 않았다면 사다리를 하나 꺼내서 설치한다.
4. 만약 사다리를 설치한 위치가 이미 방문된 곳이라면 다음 사다리를 꺼낸다.
5. 이 과정은 모든 지점 탐색이 완료될 때까지 반복한다.

import java.util.*;

class Solution {
    static class Point {
        int r;
        int c;
        int cost;
        
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
        
        public Point(int r, int c, int cost) {
            this.r = r;
            this.c = c;
            this.cost = cost;
        }
    }
    
    static int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int solution(int[][] land, int height) {
        int N = land.length;
        boolean[][] visited = new boolean[N][N];
        PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.cost));
        pq.add(new Point(0, 0));
        int visitCount = N * N;
        int totalCost = 0;
        
        while (true) {
            // 아직 모든 지점을 방문하지 않음.
            Point start = null;
            while (!pq.isEmpty()) {
                start = pq.poll();
                if (!visited[start.r][start.c]) break; 
            }
            
            Queue<Point> q = new LinkedList<>();
            q.add(start);
            visited[start.r][start.c] = true;
            totalCost += start.cost;
            visitCount--;
            
            while (!q.isEmpty()) {
                Point curr = q.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = curr.r + DIRECTION[d][0];
                    int nc = curr.c + DIRECTION[d][1];
                    
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                    if (visited[nr][nc]) continue;
                    
                    int gap = Math.abs(land[nr][nc] - land[curr.r][curr.c]);
                    if (gap <= height) {
                        q.add(new Point(nr, nc));
                        visited[nr][nc] = true;
                        visitCount--;
                    } else {
                        pq.add(new Point(nr, nc, gap));
                    }
                }
            }
            
            if (visitCount == 0) {
                return totalCost;
            }
        }
    }
    
}

코딩테스트 연습 - 튜플 | 프로그래머스 스쿨 (programmers.co.kr)

문자열 s가 표현하는 튜플을 배열에 담아 반환하시오.

예를 들어 s = “{{2}, {2,1}, {2,1,3}, {2,1,3,4}}” 이면 튜플은 (2, 1, 3,4)가 된다.

다음으로 s = "{{1,2,3}, {2,1}, {1,2,4,3}, {2}}” 역시도 튜플은 (2, 1, 3, 4)이다.

문자열을 잘 분리하는 것이 핵심이다.

"{{1,2,3}, {2,1}, {1,2,4,3}, {2}}” 를 기준으로 생각해 보자. 각 집합을 구분하는 구분자는 “,”이다. 그렇지만 “,”를 기준으로 나누면 집합 내의 ‘,’의 존재 때문에 안된다.

따라서 ”},”를 기준으로 나누면 어떨까? 우선 시작과 끝의 “{”, “}” 는 없애고 본다.

"{1,2,3}, {2,1}, {1,2,4,3}, {2”

“{1, 2, 3” , “{2, 1”, {1, 2, 4, 3”, “{2”이가 된다.

이제 이거를 숫자의 개수를 기준으로 정렬을 해야 한다.

즉 [”2”, “2, 1”, “1, 2, 3”, “1, 2, 4, 3”] 으로 만들어야 튜플을 구할 수 있다.

1. substring을 통해 문자열을 잘라낸다.
2. 그 후 구분자룰 “},”로 삼아 문자열을 배열로 분리한다.
3. 길이 순으로 오름차순 정렬을 한다.
4. Set을 통해 중복된 숫자 처리를 한다. LinkedHashSet을 사용해 삽입 순서를 유지해 해당 set을 통해 정답을 구성하겠다.

import java.util.*;

class Solution {
    public int[] solution(String s) {
        s = s.substring(1, s.length() - 2);
        String[] splited = s.split("},");
        Arrays.sort(splited, (a, b) -> Integer.compare(a.length(), b.length()));
        for (int i = 0; i < splited.length; i++) {
            splited[i] = splited[i].substring(1);           
        }
        
        Set<Integer> set = new LinkedHashSet<>();
        for (String words : splited) {
            for (String num : words.split(",")) {
                int v = Integer.parseInt(num);
                if (set.contains(v)) continue;
                set.add(v);
                break;
            }
        }
        
        return set.stream().mapToInt(Integer::intValue).toArray();
    }
}

1944번: 복제 로봇 (acmicpc.net)

모든 열쇠를 찾으면서 로봇이 움직이는 횟수의 합의 최소.

하나의 칸에 동시에 여러 로봇이 존재할 수 있다.

S와 K의 위치에서 로봇이 복제가 가능하다.

로봇은 최초에 1대 존재하며 S와 K에서 원하는 숫자만큼 복제할 수 있다.

→ 복제란 무엇이지? 최단 거리니 BFS를 생각해 보면 퍼저나 가는 모습이 마치 복제된 로봇들이 이동하는 것과 유사하다. 결국 복제는 하나의 로봇이 여러 경로로 갈 수 있다고 이야기하는 것 같다.

→ 특히 복제 한다는 부분에서 중요한 노드임을 판단할 수 있다.

결국 최단거리로 모든 열쇠를 수거해야 한다. 최단거리의 기반 알고리즘은 BFS로 하면 될 것 같다.

같은 지점을 반복해서 지나갈 수 있다.

→ 하였으므로 단순 배열로 방문 처리를 하면 안 된다. 경로 자체를 반복 가능한 간선으로 보고 각 노드를 방문 기준으로 처리해야 할 것 같다.

결국 노드와 간선으로 구성된 그래프 문제가 된다.

모든 노드를 최소 비용으로 연결하면 되는 문제가 되며 MST이다.

1. 입력을 순회하며 S, K 위치를 저장한다. = 노드가 된다.
2. 노드들 사이의 거리를 계산한다.
   1. 이게 곧 간선이다. 간선이니 시작, 도착, 거리 이렇게 세 필드가 필요하다.
   2. Edge라는 클래스에 저장하며 이 Edge들을 저장한다.
   3. 거리 계산은 한 노드에서 다른 노드들 사이 거리를 계산하는 것이다. bfs를 통해 계산한다.
3. 저장된 Edge들을 가지고 최소신장트리를 구성한다.
   1. 가장 비용(거리)이 저렴한 것부터 꺼내서 두 노드를 연결한다.
   2. 노드를 연결하는데 이미 같은 집합에 있다면 패스
      1. UNION-FIND를 통해 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static FastReader scan = new FastReader();
    static int N, M;
    static int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static char[][] map;
    static Map<String, Point> points = new HashMap<>(); // 시작점, 열쇠들이 저장될 공간
    static int[][] distances;

    static class Point {
        int id, r, c;

        Point(int id, int r, int c) {
            this.id = id;
            this.r = r;
            this.c = c;
        }

        String getKey() {
            return r + "," + c;
        }

        @Override
        public boolean equals(Object o) {

            if (!(o instanceof Point)) {
                return false;
            }
            Point p = (Point) o;

            return this.r == p.r && this.c == p.c;
        }
    }

    static class Edge implements Comparable<Edge> {
        int start, end, weight;

        Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        map = new char[N][N];
        int id = 0;
        for (int i = 0; i < N; i++) {
            map[i] = scan.next().toCharArray();
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 'S' || map[i][j] == 'K') {
                    Point point = new Point(id++, i, j);
                    points.put(point.getKey(), point);
                }
            }
        }

        int size = points.size();
        distances = new int[size][size];
        for (int[] row : distances) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
    }

    static void calculateDistances() {
        for (Point point : points.values()) {
            dfs(point);
        }
    }

    static void dfs(Point start) {
        Queue<Point> q = new LinkedList<>();
        int[][] visited = new int[N][N];
        q.add(start);
        visited[start.r][start.c] = 0;

        while (!q.isEmpty()) {
            Point curr = q.poll();
            // 시작점이 아니면서 다른 노드라면 거리 갱신
            if (!start.equals(curr) && points.containsKey(curr.getKey())) {
                int from = start.id;
                int to = points.get(curr.getKey()).id;
                int dist = visited[curr.r][curr.c];
                distances[from][to] = dist;
                distances[to][from] = dist;
            }

            for (int d = 0; d < 4; d++) {
                int nr = curr.r + DIRECTION[d][0];
                int nc = curr.c + DIRECTION[d][1];

                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    continue;
                }
                if (visited[nr][nc] != 0) {
                    continue;
                }
                if (map[nr][nc] == '1') {
                    continue;
                }

                q.add(new Point(-1, nr, nc));
                visited[nr][nc] = visited[curr.r][curr.c] + 1;
            }
        }
    }

    private static int getShortestPath() {
        PriorityQueue<Edge> edges = new PriorityQueue<>();
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                if (distances[i][j] != Integer.MAX_VALUE) {
                    edges.add(new Edge(i, j, distances[i][j]));
                }
            }
        }
        int[] parent = new int[points.size()];
        for (int i = 0; i < points.size(); i++) {
            parent[i] = i;
        }
        int sum = 0;
        int connected = 0;
        while (!edges.isEmpty()) {
            Edge edge = edges.poll();
            int start = edge.start;
            int end = edge.end;

            if (find(parent, start) != find(parent, end)) {
                union(parent, start, end);
                sum += edge.weight;
                connected++;
            }
        }

        // 만약 모든 노드들을 연결하지 못했다면 -1 반환
        if (connected != points.size() - 1) {
            return -1;
        }
        return sum;
    }

    private static int find(int[] parent, int node) {
        if (parent[node] != node) {
            parent[node] = find(parent, parent[node]);
        }

        return parent[node];
    }

    private static void union(int[] parent, int node1, int node2) {
        int root1 = find(parent, node1);
        int root2 = find(parent, node2);

        if (root1 != root2) {
            parent[root1] = root2;
        }
    }

    public static void main(String[] args) {
        input();
        calculateDistances();
        int result = getShortestPath();
        System.out.println(result);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Surrounded Regions - LeetCode

‘X’, ‘O’로 이루어진 m x n 2차원 배열이 있다.

사방이 ‘X’로 둘러 쌓여있는 ‘O’들은 ‘X’로 변경한 결과를 반환하라.

‘X’는 언제 ‘O’로 변경되는가? ‘O’가 ‘X’로 둘러 쌓여 있을 때 변경된다.

가장자리의 ‘O’에 연결된 부분은 절대로 ‘X’로 바뀌지 않는다. 그 이외의 ‘O’들은 전부 ‘X’로 바뀔 수밖에 없다.

즉 가장자리에 존재하는 ‘O’ 부터 시작해서 탐색을 진행하며 해당 위치를 별도로 표기해 두고 나머지를 전부 ‘X’로 채우면 된다.

1. 가장자리를 탐색하면서 ‘O’라면 탐색을 시작한다.
2. 탐색 과정에서는 ‘O’를 임시로 ‘A’로 바꿔놓는다.
3. 모든 탐색이 끝난 후 ‘X’로 가득 차 있는 2차원 배열에서 ‘A’의 위치를 ‘O’로 변경해 리턴한다.

class Solution {
    static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public void solve(char[][] board) {
        Set<int[]> startPoints = getStartPoints(board);
        for (int[] startPoint : startPoints) {
            dfs(startPoint, new boolean[board.length][board[0].length], board);
        }

        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (board[r][c] =='O') {
                    board[r][c] = 'X';
                } else if (board[r][c] == 'A') {
                    board[r][c] = 'O';
                }
            }
        }
    }

    private void dfs(int[] currPoint, boolean[][] visited, char[][] board) {
        int r = currPoint[0];
        int c = currPoint[1];
        board[r][c] = 'A';
        visited[r][c] = true;

        for (int d = 0; d < 4; d++) {
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];

            if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;
            if (board[nr][nc] == 'O' && !visited[nr][nc]) {
                dfs(new int[]{nr, nc}, visited, board);
            }
        }
    }

    private Set<int[]> getStartPoints(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        Set<int[]> result = new HashSet<>();
        for (int row : List.of(0, n - 1)) {
            for (int col = 0; col < m; col++) {
                if (board[row][col] == 'O') {
                    result.add(new int[]{row, col});
                }
            }
        }

        for (int col : List.of(0, m - 1)) {
            for (int row = 0; row < n; row++) {
                if (board[row][col] == 'O') {
                    result.add(new int[]{row, col});
                }
            }
        }

        return result;
    }
}