프로그램을 실행시키면, OS는 해당 프로그램을 프로세스 형태로 관리함.

프로세스 API: 프로그래머가 프로세스를 생성, 제어, 모니터링할 수 있도록 OS가 제공하는 함수(시스템 콜)들의 집합. Unix 계열 시스템에서는 fork(), exec(), wait() 등이 있다.

fork(): 새로운 프로세스 만들기

• 기능: fork()는 현재 프로세스를 복사하여 "자식 프로세스"를 하나 더 만듦.
• 동작 원리:
  호출한 시점에서 프로세스가 두 개로 나뉨.
  • 부모 프로세스: 기존 프로세스
  • 자식 프로세스: 부모의 복사본
• 반환값 차이:
  • 부모 프로세스: fork()가 자식 프로세스의 PID(프로세스 ID)를 반환
  • 자식 프로세스: fork()가 0을 반환
• 결과:
  이렇게 반환값의 차이를 이용해 부모와 자식에서 각각 다른 코드를 실행.

예제 코드:

int rc = fork();
if (rc < 0) {
    fprintf(stderr, "fork failed\n");
    exit(1);
} else if (rc == 0) {
    // 자식 프로세스 영역
    printf("I am the child process!\n");
} else {
    // 부모 프로세스 영역
    printf("I am the parent process, child pid = %d\n", rc);
}

exec(): 다른 프로그램 실행하기

• 기능: exec() 계열 함수(execvp, execl, execve 등)는 현재 프로세스를 완전히 다른 프로그램으로 대체.
• 사용 시나리오: fork()를 통해 자식을 만들었는데, 그 자식이 부모와 똑같은 프로그램을 실행하는 대신 전혀 다른 프로그램을 실행하고 싶을 때 호출.
• 동작 원리:
  • exec()가 성공하면 기존에 로드되어 있던 코드와 데이터가 새로운 프로그램으로 덮어씌어짐.
  • exec()는 성공한 뒤 원래 코드로 돌아오지 않으며, 바로 새로운 프로그램의 main()부터 실행.

예제 코드 (자식에서 wc 명령 실행):

int rc = fork();
if (rc == 0) { 
    // 자식 프로세스
    char *args[] = {"wc", "filename.txt", NULL};
    execvp(args[0], args);
    // 여기까지 도달하지 않음 (exec 성공 시)
    fprintf(stderr, "exec failed\n");
    exit(1);
}

wait(): 자식 프로세스 종료 대기

• 기능: wait()는 부모 프로세스가 자식 프로세스가 끝날 때까지 기다리게 하는 시스템 콜.
• 사용 이유:
  • 부모 프로세스가 자식의 수행 결과를 필요로 할 때
  • 자식이 종료되기 전에 부모가 먼저 종료해버리면 자식이 "고아 프로세스"가 될 수 있으므로, 이를 방지하기 위해 사용
• 반환값: 종료한 자식의 PID를 반환(어떤 자식이 끝났는 지 알 수 있음).

예제:

int rc = fork();
if (rc == 0) {
    // 자식 프로세스
    printf("Child running...\n");
    sleep(2); // 예: 2초 후 종료
    exit(0);
} else {
    // 부모 프로세스
    int wc = wait(NULL); // 자식이 끝날 때까지 대기
    printf("Child %d finished\n", wc);
}

왜 이렇게 복잡할까? (fork + exec 조합의 이유)

• 유연성 확보:
  자식 프로세스를 만든 후 exec()를 호출하기 전까지 환경을 마음대로 설정할 수 있다.
  ex) 자식 프로세스에서 파일 디스크립터를 재지정하여 표준 출력이 화면 대신 파일로 가게 하거나, 파이프를 이용해 다른 프로세스와 연동 등등..
• 쉘의 구현:
  쉘(shell): 사용자가 입력한 명령어를 실행하는 프로그램.
  fork()로 자식을 만든 뒤, 그 자식 안에서 exec()를 호출하여 사용자가 입력한 명령어 실행.
  이 과정에서 I/O 재지정, 파이프, 환경 변수 설정 등등 가능..

추가적인 프로세스 관련 API와 개념

• kill(): 특정 프로세스에 시그널을 보내 프로세스를 종료, 중단, 재개하는 등.
• ps, top: 현재 실행 중인 프로세스를 모니터링하고 CPU, 메모리 사용량을 확인.
• nice(): 프로세스의 우선순위를 조정.
• setsid(), setpgid(): 프로세스를 세션이나 프로세스 그룹으로 묶어 제어.
• 파이프(pipe) & 리다이렉션(>), <): 파이프를 통해 한 프로세스의 출력을 다른 프로세스의 입력으로 연결하거나, 명령어 실행 결과를 파일로 저장하는 등 다양한 입출력을 조작.

다른 운영체제와 비교

• Windows:
  Windows는 CreateProcess()라는 단일 API 콜로 새로운 프로세스 생성과 프로그램 로딩을 함께 처리. (CreateProcess() 하나로 프로세스 생성 및 실행)
• 멀티스레드 환경:
  fork()는 호출 시점의 스레드와 메모리 상태를 복사 → 스레드 안전성 문제 fork() 직후 exec()를 바로 호출하는 것이 권장된다.

GPT님님님의 의견

멀티스레드 프로그램에서 fork()를 호출할 경우 다음과 같은 문제가 발생할 수 있습니다:

1. 스레드 복제 방식:
   fork()는 호출한 스레드를 포함한 전체 프로세스의 메모리 상태를 복사하지만, 실제로 새로 생성된 자식 프로세스에는 호출한 스레드 하나만 존재하게 됩니다. 즉, 부모 프로세스에는 여러 스레드가 있었지만, fork() 후 자식 프로세스에는 단 하나의 스레드(호출한 스레드)만 남게 됩니다. 이 과정에서 다른 스레드들이 잡고 있던 락(lock)이나 공유 자원에 대한 접근 상태, 전역 변수 상태 등은 그대로 복사되지만 정작 그 스레드들은 존재하지 않습니다. 결과적으로 일부 리소스나 락이 "해제 불가능한 상태"가 되거나 비정상적인 동기화 상태에 빠질 수 있습니다.
2. 동기화 상태 불일치:
   멀티스레드 프로그램은 락, 조건 변수, 뮤텍스, 세마포어 등의 동기화 기법으로 스레드 간 자원 접근을 조율합니다. fork()를 통해 복사된 자식 프로세스는 메모리 상에서 동기화 객체의 상태를 그대로 물려받지만, 실제로 락을 잡고 있던 스레드는 사라졌으므로 해당 락은 유령 상태(잠긴 상태에서 더는 풀 수 없는 상태)가 될 수 있습니다. 또한 조건 변수가 특정 스레드를 깨우기 위한 신호를 기다리고 있는 상태일 때, 그 스레드는 더 이상 존재하지 않으므로 조건을 충족할 수 없는 교착 상태가 발생할 수 있습니다.
3. 해결책 – fork() 후 즉시 exec():
   이러한 문제를 피하기 위해, 표준 C 라이브러리와 POSIX 표준에서는 멀티스레드 환경에서 fork()를 호출한 뒤에는 가능한 한 빠르게 exec() 계열 함수를 호출하여 완전히 새로운 프로그램 이미지로 전환하는 것을 권장합니다. exec()를 호출하면 기존 메모리 공간(및 그 안에서 뒤틀린 동기화 상태)을 모두 버리고 새 프로그램의 깨끗한 메모리 상태로 시작하기 때문에 스레드 안전성 문제를 근본적으로 해소할 수 있습니다.

정리하자면, 멀티스레드 환경에서 fork()를 호출하면 부모 프로세스의 복잡한 스레드 및 동기화 상태가 그대로 복사되지만 실제로 자식 프로세스에는 한 스레드만 남기 때문에, 동기화 객체와 공유 자원 상태가 비정상적이고 예측 불가능한 상황에 놓일 수 있습니다. 이를 피하기 위해 자식 프로세스에서 곧바로 exec()를 호출하여 새 프로그램 이미지를 로드하는 것이 안전한 패턴입니다.

📒 문제

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

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다. 

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. 

M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.

입력

첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1≤N≤100000, 1≤M≤10)
둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.
단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

출력

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
using namespace std;
int n, m;
vector <string> voca;
map<string, int> mp;
string v;
bool compare(string a, string b) {
    if (a.size() == b.size() && mp[a] == mp[b]) {
        return a < b;
    }
    else if (mp[a] == mp[b]) {
        return a.size() > b.size();
    }
    return mp[a] > mp[b];
}

int main() {
    
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> v;
        if (v.size() < m) continue;
        if (mp.find(v)==mp.end()) {
            mp[v] = 0;
            voca.push_back(v);
        }
        mp[v]++;
    }
    sort(voca.begin(), voca.end(), compare);

    for (int i = 0; i < voca.size(); i++) {
        cout << voca[i] << '\n';
    }
}

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

public class Main {

    static class Meeting implements Comparable<Meeting> {
        int start, end, people;

        Meeting(int start, int end, int people) {
            this.start = start;
            this.end = end;
            this.people = people;
        }

        @Override
        public int compareTo(Meeting o) {
            return this.end - o.end; // 종료 시간 기준 정렬
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());

        Meeting[] meetings = new Meeting[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int people = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end, people);
        }

        // 종료 시간 기준 정렬
        Arrays.sort(meetings);

        // DP 배열 및 종료 시간 배열
        int[] dp = new int[n];
        int[] endTimes = new int[n];

        for (int i = 0; i < n; i++) {
            endTimes[i] = meetings[i].end; // 종료 시간만 저장
        }

        dp[0] = meetings[0].people; // 첫 회의 인원 초기화

        for (int i = 1; i < n; i++) {
            // 현재 회의 인원
            dp[i] = meetings[i].people;

            // 이전 회의 중 겹치지 않는 가장 마지막 회의 찾기 (이분 탐색)
            int idx = binarySearch(endTimes, meetings[i].start);
            if (idx != -1) {
                dp[i] += dp[idx];
            }

            // 이전 최대값과 비교
            dp[i] = Math.max(dp[i], dp[i - 1]);
        }

        System.out.println(dp[n - 1]);
    }

    // 이분 탐색: 종료 시간이 target 이하인 가장 마지막 인덱스를 찾음
    private static int binarySearch(int[] endTimes, int target) {
        int left = 0, right = endTimes.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (endTimes[mid] <= target) {
                result = mid; // 가능한 인덱스 갱신
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

1. 자바의 메모리 구조

메서드 영역

메서드 영역은 프로그램을 실행하는데 필요한 공통 데이터를 관리한다. 이 영역은 프로그램의 모든 영역에서 공유한다.

• 클래스 정보: 클래스의 실행코드(바이트 코드), 필드, 메서드와 생성자 코드 등 모든 실행 코드가 존재한다.
• static 영역: static 변수들을 보관한다.
• 런타임 상수 풀: 프로그램을 실행하는데 필요한 공통 리터럴 상수를 보관한다.

스택 영역

스택 영역은 자바 실행 시 생성이 되는데, 스레드 1개당 하나의 스택이 생성된다. 그리고 메소드가 호출될 때마다 스택 영역에는 스택 프레임이 하나씩 쌓이게 된다.

• 스택 프레임: 지역 변수(매개변수 포함), 중간 연산 결과, 메소드 호출 정보 등을 포함한다.
  - Local Variables: 메소드의 지역 변수들을 갖는다.
  - Operand Stack: 메소드 내 계산을 위한 작업 공간이다.
  - Constant Pool Reference: 런타임 상수 풀의 참조를 갖는다.

힙 영역

힙 영역은 인스턴스와 배열이 생성되는 곳이다. 가비지 컬렉션(GC)이 주로 이루어지며 더 이상 참조되지 않는 객체는 GC에 의해 청소된다. 쓱싹.

👶 인스턴스는 내부에 변수와 메서드를 가지고 있는데, 그럼 각각의 인스턴스의 메서드는 인스턴스가 생성될 때마다 인스턴스 영역에 들어가게 되는지,,?
👩🏻‍💻 인스턴스들의 필드 값은 모두 다른 주소를 가져야겠지만, 메소드의 코드는 모두 동일합니다. 따라서 메서드는 메서드 영역에서 공통으로 관리됩니다. 즉, 인스턴스의 메서드를 호출하면 힙영역이 아닌 메서드 영역에 있는 코드가 호출이 됩니다.

2. Static 변수 (정적 변수)

static 키워드가 붙는 변수는 모두 메서드 영역(스태틱 영역)에서 관리가 된다. 즉, 인스턴스 영역에 생성되지 않는 것이다.

위와 같이 인스턴스와 함께 생성이 되지 않기 때문에 현재까지 인스턴스를 몇 개를 만들었는지 확인하는 static int count 변수가 사용 가능하다. 즉, 스태틱 변수는 클래스 하나당 하나만 생성이 되며 인스턴스 변수는 인스턴스의 수만큼 생성이 된다.

변수와 생명주기

• 지역 변수(매개변수 포함): 스택 영역의 스택 프레임에 저장되며 메서드가 종료되면 프레임이 제거됨과 동시에 제거된다.
• 인스턴스 변수: 힙 영역에 저장되며 인스턴스가 개발자에 의해 제거되거나 GC가 발생하기 전까지 생존한다.
• 클래스 변수(스태틱 변수, 정적 변수): 메서드 영역의 static 영역에 저장되며 JVM 로딩과 함께 생성되며 JVM이 종료되면 함께 생명이 끝난다.

Static 변수 접근법

1. 인스턴스를 통해 접근

Data data = new Data();
data.count++;

2. 클래스를 통한 접근

Data.count++;

스태틱 변수는 클래스 변수라고 불리는 만큼 클래스를 통해 접근하는 것이 가독성이 훨씬 좋다. 인스턴스 변수에 접근하는 것처럼 보이는 것 보다 한눈에 명확히 클래스 변수에 접근하는 것처럼 보이는 것이 더욱 명확하기 때문이다.

3. Static 메서드 (정적 메서드)

Static 메서드는 정적 변수와 마찬가지로 스태틱 영역에서 관리된다. 따라서 마찬가지로 인스턴스 생성 없이 클래스 명을 통해 호출이 가능하다.

public class Math() {

	public static int add(int a, int b) {
    	return a+b;
    }
    
    public static int subtract(int a, int b) {
    	return a-b;
    }
}

위와 같은 유틸리티 클래스(Utility Class, 정적 메서드만 존재하는 클래스)에서 이러한 접근법은 유용하게 쓰인다.

정적 메서드 접근법

1. 인스턴스를 통해 접근

Math math = new Math();
math.sum(1, 2);

2. 클래스명을 통해 접근

Math.sum(1, 2);

3. static import를 통해 접근 (정적 변수도 import 가능)

import static 패키지명.Math.*;

sum(1, 2);

정적 메서드 사용 시 주의할 점

static 메서드는 static 만 사용 할 수 있다.

생각해보면 당연하다. 정적 메서드는 참조값이 없다. 그런데 인스턴스 변수나 메서드를 사용하려면 참조값을 알아야한다. 따라서 정적 메서드에서 인스턴스 변수나 메서드를 불러오면 자바는 어느 주소를 찾아가야 하는지 알 수 없게 되고(참조값 부재), 컴파일 에러가 뜨게 된다.

4. main() 메서드

인스턴스 생성 없이 사용하는 메서드의 가장 대표적인 예는 main() 메서드이다. 따라서 main에서 호출할 메서드 또한 모두 static 이어야 한다. 변수 또한 마찬가지다.

정적 변수를 작성해서 에러가 나는 경우

public class Math() {
	public int count;
    
    public static void main(String[] args) {
    	count++;
    }
}

정적 메서드를 사용해서 에러가 나는 경우

public class Math() {

    public static void main(String[] args) {
    	test();
    }
    
    public void test() {
    	System.out.println("test!");
    }
}

문제 캡처

소스 코드

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class Main {

    static Comparator<Integer> comparator(Map<Integer, Integer> map) {
        return (key1, key2) -> {
            int value1 = map.get(key1), value2 = map.get(key2);
            if(value1 == value2) {
                return key1 - key2;
            }
            return value1 - value2;
        };
    };

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int r = Integer.parseInt(st.nextToken())-1,
        c = Integer.parseInt(st.nextToken())-1,
        k = Integer.parseInt(st.nextToken());

        int[][] arr = new int[101][101];

        for(int i=0;i<3;i++) {
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<3;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int time = 0;
        int rowCnt = 3, colCnt = 3;
        while(arr[r][c] != k && time <= 100) {
            time++;
            if(rowCnt >= colCnt) {
                int col = colCnt;
                //R연산
                for(int i=0;i<rowCnt;i++) {
                    Map<Integer, Integer> freqMap = new HashMap<>();
                    //행 연산 실행
                    for(int j=0;j<colCnt;j++) {
                        if(arr[i][j] == 0) continue;
                        freqMap.put(arr[i][j], freqMap.getOrDefault(arr[i][j], 0)+1);
                    }
                    TreeMap<Integer, Integer> sortMap = new TreeMap<>(comparator(freqMap));
                    sortMap.putAll(freqMap);
                    int nowColCnt = sortMap.size()*2;
                    for(int j=0;j<nowColCnt;j+=2) {
                        Entry<Integer, Integer> value = sortMap.pollFirstEntry();
                        arr[i][j] = value.getKey();
                        arr[i][j+1] = value.getValue();
                    }
                    for(int j=nowColCnt;j<colCnt;j++) {
                        arr[i][j] = 0;
                    }
                    col = Math.max(col, nowColCnt);
                }
                colCnt = col;
            } else {
                int row = rowCnt;
                //C연산
                for(int j=0;j<colCnt;j++) {
                    Map<Integer, Integer> freqMap = new HashMap<>();
                    //열 연산 실행
                    for(int i=0;i<rowCnt;i++) {
                        if(arr[i][j] == 0) continue;
                        freqMap.put(arr[i][j], freqMap.getOrDefault(arr[i][j], 0)+1);
                    }
                    TreeMap<Integer, Integer> sortMap = new TreeMap<>(comparator(freqMap));
                    sortMap.putAll(freqMap);
                    int nowRowCnt = sortMap.size()*2;
                    for(int i=0;i<nowRowCnt;i+=2) {
                        Entry<Integer, Integer> value = sortMap.pollFirstEntry();
                        arr[i][j] = value.getKey();
                        arr[i+1][j] = value.getValue();
                    }
                    for(int i=nowRowCnt;i<rowCnt;i++) {
                        arr[i][j] = 0;
                    }
                    row = Math.max(row, nowRowCnt);
                }
                rowCnt = row;
            }
        }
        
        System.out.println(time>100 ? -1 : time);

    }
}

문제 캡처

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static class Loc {
        int r, c;
        
        Loc(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static List<Loc> viruses = new ArrayList<>();
    static int N, M, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}, arr[][];
    static boolean[][] visited;
    static int minTime = Integer.MAX_VALUE;
    static int emptyCount = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][N];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<N;j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 2) {
                    viruses.add(new Loc(i, j));
                } else if(arr[i][j] == 0) {
                    emptyCount++;
                }
            }
        }

        activateVirus(-1, 0, new int[M]);
        System.out.println(minTime == Integer.MAX_VALUE ? -1 : minTime);
    }

    private static void activateVirus(int index, int cnt, int[] selected) {
        if(cnt == M) {
            getTime(selected);
            return;
        }

        for(int i=index+1;i<viruses.size();i++) {
            selected[cnt] = i;
            activateVirus(i, cnt+1, selected);
        }
    }

    private static void getTime(int[] selected) {
        Queue<Loc> queue = new ArrayDeque<>();
        visited = new boolean[N][N];
        int[][] times = new int[N][N];
        int infected = 0;
        int maxTime = 0;

        // 선택된 바이러스 위치 큐에 넣기
        for(int i : selected) {
            Loc virus = viruses.get(i);
            queue.offer(virus);
            visited[virus.r][virus.c] = true;
        }

        while(!queue.isEmpty()) {
            Loc cur = queue.poll();
            
            for(int d=0;d<4;d++) {
                int nx = cur.r + dx[d];
                int ny = cur.c + dy[d];
                
                if(isInRange(nx, ny) && !visited[nx][ny] && arr[nx][ny] != 1) {
                    visited[nx][ny] = true;
                    times[nx][ny] = times[cur.r][cur.c] + 1;
                    queue.offer(new Loc(nx, ny));
                    
                    if(arr[nx][ny] == 0) {
                        infected++;
                        maxTime = Math.max(maxTime, times[nx][ny]);
                    }
                }
            }
        }

        // 모든 빈 칸이 감염되었는지 확인
        if(infected == emptyCount) {
            minTime = Math.min(minTime, maxTime);
        }
    }

    private static boolean isInRange(int i, int j) {
        return 0 <= i && i < N && 0 <= j && j < N;
    }
}

문제 캡처

소스 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    int count = 0;
    for (size_t i = 0; i < s.size(); i += 3) {
        string chunk = s.substr(i, 3);
        string target = "PER";
        for (int j = 0; j < 3; ++j) {
            if (chunk[j] != target[j]) {
                ++count;
            }
        }
    }

    cout << count << endl;
    return 0;
}

Comment…💭

문제 캡처

소스 코드

package baekjoon;

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

public class 양치기꿍_3187 {
    static char[][] map;
    static boolean[][] visited;
    static int R, C, vCnt, kCnt, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    static class Loc {
        int x, y;

        Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static Queue<Loc> queue;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken());
        map = new char[R][C]; visited = new boolean[R][C];

        for(int i=0;i<R;i++) {
            map[i] = bf.readLine().toCharArray();
        }

        int vAns = 0, kAns = 0;

        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(!visited[i][j] && map[i][j] != '#') {
                    visited[i][j] = true;
                    vCnt = 0; kCnt = 0;
                    if(map[i][j] == 'v') vCnt++;
                    if(map[i][j] == 'k') kCnt++;

                    queue = new ArrayDeque<>();
                    queue.offer(new Loc(i, j));

                    while(!queue.isEmpty()) {
                        Loc loc = queue.poll();
                        for(int idx = 0; idx < 4; idx++) {
                            int x = loc.x + dx[idx], y = loc.y + dy[idx];
                            if(!isInRange(x, y)) continue;
                            if(!visited[x][y]) {
                                visited[x][y] = true;
                                if(map[x][y] == '#') continue;
                                queue.offer(new Loc(x, y));
                                if(map[x][y] == 'v') vCnt++;
                                if(map[x][y] == 'k') kCnt++;
                            }
                        }
                    }
                    
                    if(kCnt > vCnt) {
                        kAns += kCnt;
                    } else {
                        vAns += vCnt;
                    }
                }
            }
        }
        System.out.println(kAns+" "+vAns);
    }
    static boolean isInRange(int x, int y) {
        return 0 <= x && x < R && 0 <= y && y < C;
    }

}

Comment…💭

• bfs만 돌리면 된다!
• 좀만 수정하면 코드길이와 메모리를 줄일 수 있을 것 같지만 시간이없다!