이것저것 개발 블로그

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

풀이)

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

public class Main_BJ_2583_영역구하기 {
    static int n, m, sum;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Integer> areas = new ArrayList<>();
    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());
        int k = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];
        for(int i=0; i<k; i++){
            st = new StringTokenizer(br.readLine());
            int ly = Integer.parseInt(st.nextToken());
            int lx = Integer.parseInt(st.nextToken());
            int ry = Integer.parseInt(st.nextToken());
            int rx = Integer.parseInt(st.nextToken());
            for(int x=lx; x<rx; x++){
                for(int y=ly; y<ry; y++){
                    visited[x][y] = true;
                    map[x][y]++;
                }
            }
        }//k

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(!visited[i][j]) {
                    int area = bfs(i, j);
                    sum++;
                    areas.add(area);
                }
            }
        }
        System.out.println(sum);
        Collections.sort(areas);
        for(int i=0; i<areas.size(); i++)
            System.out.print(areas.get(i)+" ");

    }//main
    private static int bfs(int x, int y){
        int area = 0;
        visited[x][y] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {x, y});

        while(!q.isEmpty()){
            int[] cur = q.poll();
            area++;
            for(int i=0; i<4; i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(check(nx, ny) && !visited[nx][ny]){
                    q.offer(new int[] {nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }//while
        return area;
    }//bfs
    private static boolean check(int x, int y) {
        if(x<0 || y<0 || x>=n || y>=m)
            return false;
        return true;
    }
}

만약, 완탐과 dfs, bfs 문제를 많이 풀어봤다면 문제 자체는 어렵지 않다!

다만,,,, 조건을 좀 많이 주의해야해서...ㅎ

처음에는 너무 단순히 아래를 0,0 을 잡았다해서 위 아래만 바뀐거라 괜찮아~~ 했는데,,

1. 행과 열이 바뀌어 있는 문제입니다....

2. 최소 좌표와 최대 좌표가 있는데, 최대 좌표를 -1 만큼 탐색하면 일반 탐색과 다를 것이 없습니다.

나머지는 입력을 받으면서 직사각형을 그린 영역을 visited 처리해주고,

전체 완탐을 하면서 visited 안 한 곳을 찾아주면 된다!

bfs를 통해 visited가 아닌 곳의 영역 수를 구하면 되고, 이는 bfs의 return값을 이용하여 영역을 저장해준다.

그리고 areas라는 ArrayList 배열을 정렬하면 끝!!

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

풀이)

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

public class Main_BJ_2178_미로탐색 {
    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static int[][] sum;
    //상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static class Point{
        int x;
        int y;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    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];
        visited = new boolean[n][m];
        sum = new int[n][m];

        for(int i=0; i<n; i++){
            String str = br.readLine();
            for(int j=0; j<m; j++){
                map[i][j] = str.charAt(j)-'0';
            }
        }

        bfs();
        System.out.println(sum[n-1][m-1]);

    }//main
    private static void bfs(){
        Queue<Point> q = new ArrayDeque<>();
        Point start = new Point(0, 0);
        q.offer(start);
        visited[start.x][start.y] = true;
        sum[start.x][start.y] = 1;

        while (!q.isEmpty()){
            Point cur = q.poll();
            if(cur.x == n-1 && cur.y == m-1)
                break;

            for(int i=0; i<4; i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(check(nx, ny) && !visited[nx][ny] && map[nx][ny] == 1){
                    q.offer(new Point(nx, ny));
                    visited[nx][ny] = true;
                    sum[nx][ny] = sum[cur.x][cur.y] + 1;
                }
            }
        }


    }//bfs
    private static boolean check(int x, int y){
        if(x<0 || x>=n || y<0 || y>=m)
            return false;
        return true;
    }
}

그래프 탐색의 가장 기본적인 유형 아닐까 싶다.

이렇게 간단할땐 class를 만들기도 하지만(눈에 보기 깔끔해서) 배열을 냅다 큐에 넣기도 했는데,

본인만 편하게 한다면 관계 없을 것 같다.

그래프 탐색 처음인 사람들이 풀면 좋은 문제일듯!

class 만들기 복습하는 계기가 되었다!

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

풀이)

진짜 겁나 틀린 문제...! 꼼꼼히 풀어야 한다는 교훈을 얻었다.

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

public class Main_BJ_16928_뱀과사다리게임 {
    static int[] map = new int[101];
    static int[] snakeLadder = new int[101];
    static boolean[] visited = new boolean[101];

    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 m = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            snakeLadder[a] = b;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            snakeLadder[a] = b;
        }

        bfs();
        System.out.println(map[100]);
    }//main

    private static void bfs() {
       Queue<Integer> q = new ArrayDeque<>();
       //처음 시작은 무조건 1
       q.add(1);
       visited[1] = true;

       while(!q.isEmpty()){
           int cur = q.poll();
           //주사위: 한 번에 6칸 이동
           for(int i=1; i<=6; i++){
               int nx = cur+i;
               //다음 좌표가 100보다 작거나 같아야 하고, 방문하지 않았어야함
               if(nx <= 100 && !visited[nx]){
                   //다음 좌표가 사다리를 타고 이동할 수 있을 때 && 이동한 좌표가 방문한 적 없을 때
                   if(snakeLadder[nx] != 0 && !visited[snakeLadder[nx]]){
                       // 큐에 저장, 이동 거리 작성, 방문처리
                       q.offer(snakeLadder[nx]);
                       map[snakeLadder[nx]] = map[cur] + 1;
                       map[nx] = map[cur] + 1;
                       visited[nx] = true;
                       visited[snakeLadder[nx]] = true;
                   }
                   //다음 좌표가 사다리가 없을 때
                   else if(snakeLadder[nx] == 0){
                       //다음 좌표 큐에 저장, 이동 거리 작성, 방문처리
                       map[nx] = map[cur] + 1;
                       q.offer(nx);
                       visited[nx] = true;
                   }
               }
           }
       }//while
    }//bfs
}

주요 논리는 주석에 작성했다.

처음에는 좀 많이 헤맸는데, 그럴필요 없다는걸 다른 글을 보며 읽었다.

틀린 부분은 질문 게시판의 반례를 보면서 찾았음..ㅠ

담엔 더 꼼꼼히 보자 화이팅!

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

문제)

해설)

이 문제는 당연히 bfs로 풀어야지!! 하면서 좀 헤맸다..ㅎㅎ

두 가지 방식으로 했는데, 코드는 두 번째가 조금 더 깔끔한 것 같다.

풀이 1)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    count = 0
    while tomato:
        second = []
        t_li = tomato.popleft()
        for t_mem in t_li:
            x, y = t_mem[0], t_mem[1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if box[nx][ny] == 0:
                        second.append([nx, ny])
                        box[nx][ny] = 1
                    else:
                        continue
        if second != []:
            tomato.append(second)
        count += 1
    return count - 1

m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

first = []
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            first.append([i, j])
tomato.append(first)


day = bfs(tomato)
for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            print(-1)
            exit(0)
print(day)

bfs 함수 내에서 며칠이나 걸렸는지 반환해주려고 이 코드를 짜게 되었다.

한 박스에 토마토가 여러 개일 경우 동시에 토마토가 있는 좌표의 옆 토마토들이 익는다.

따라서 하루 단위로 익을 토마토(box에서 0인 애들) list(first, second)를 만들어 저장하고, 그것을 tomato라는 queue에 저장하는 방식으로 구현했다.

tomato에서 하나를 뽑으면 그 list에 해당하는 좌표를 순회하고, 해당 list에 저장된 좌표를 모두 돌면 하루가 늘어나는 방식이다.

하지만 여기에는 처음에 토마토가 있던 위치도 하루가 지난 것으로 치는 방식이기에 1을 뺀 값을 반환한다.

bfs가 모두 끝나면 혹시 토마토가 익지 않은 경우가 있을 수 있기 때문에 확인해준다.

여기에서 익지 않은 토마토가 있을 경우 -1을 출력하고 exit 하여 끝낸다.

그렇지 않다면 bfs 결과를 출력해준다.

풀이 2)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    while tomato:
        x, y = tomato.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if box[nx][ny] == 0:
                    tomato.append([nx, ny])
                    box[nx][ny] = box[x][y] + 1
                else:
                    continue


m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            tomato.append([i, j])


day = 0
bfs(tomato)
for i in box:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    day = max(day, max(i))
print(day - 1)

이 풀이도 똑같이 bfs를 활용했다.

다른 점은 좌표를 차례대로 queue인 tomato에 저장해주고, bfs를 하는 도중 다음 좌표의 box 값이 0이라면 원좌표의 값에 +1을 해주는 방식을 사용했다. 

또한 이 방식도 처음 토마토의 위치가 1이어서 하루가 더 더해진 방식이므로 box에 0이 없음을 확인하면 1을 뺀 값을 출력해준다.

DFS(Depth-First Search, 깊이 우선 탐색)

그래프에서 깊은 부분을 우선적을 탐색하는 알고리즘. 스택(stack)을 사용한다!

동작 과정:

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

2번 과정에서 방문하지 않은 인접 노드를 스택에 넣을 때 순서는 상관없지만, 문제에 따라서 알파벳 순서 또는 작은 숫자 순서대로 가는 경우가 많으므로 작은 노드 순서대로 넣는 경우가 많다.

그럼 실습해보자!!

def dfs(graph, v, visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# DFS 호출
dfs(graph, 1, visited)


### 출력 결과(stack에 들어간 순서대로): 1 2 5 6 7 3 4

BFS(Breath-First Search, 너비 우선 탐색)

가까운 노드부터 탐색하는 알고리즘. 큐(queue)를 사용한다!

동작 과정:

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS와 마찬가지로 작은 노드부터 수행하는 경우가 많다!

위에 있는 그래프를 이용하여 다시 실습해보자!

from collections import deque

# BFS 정의
def bfs(graph, start, visited):
    # queue 구현 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = ' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3],
    [1, 5],
    [1, 4],
    [3],
    [2, 6, 7],
    [1, 5],
    [5]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 8
# BFS 호출
bfs(graph, 1, visited)


### 출력 결과(큐에 삽입된 순서대로): 1 2 3 5 4 6 7