Problem


특정 조건에 따라 움직이는 로봇이 청소한 칸의 총 갯수를 구하는 문제입니다.



Solution

로봇이 청소한 구역을 구하는 문제입니다.


특별한 알고리즘 없이 문제에서 주어진 조건대로 구현하는 시뮬레이션 문제입니다.


북, 동, 남, 서 방향에 대한 계산만 헷갈리지 않고 해주면 쉽게 구현할 수 있습니다.


현재 로봇의 위치와 방향에 대한 정보를 잘 관리해야 합니다.


로봇에 대한 클래스를 만들어도 되지만 그냥 전역 변수로 처리하였습니다.


한가지 특이한 점은 맵의 테두리는 항상 벽으로 되어 있어 map 배열이 범위를 벗어나는 경우는 처리하지 않아도 됩니다.



Java Code

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

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int n, m;
    static int[][] map;
    static int r, c, d;
    static int[] dx = {-1, 0, 1, 0};    // 북동남서
    static int[] dy = {0, 1, 0, -1};
    static int turnCount = 0;

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

        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        map = new int[n][m];

        st = new StringTokenizer(br.readLine());
        r = stoi(st.nextToken());
        c = stoi(st.nextToken());
        d = stoi(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = stoi(st.nextToken());
            }
        }

        solution();
    }

    static void solution() {
        /**
         * 0 : 청소하지않은 공간
         * 1 : 벽
         * 2 : 청소한 공간
         */

        while (true) {
            if (turnCount == 4) {
                // 네 방향 모두 청소가 되어있거나 이미 벽이면 후진 후 2번으로
                int backX = r - dx[d];
                int backY = c - dy[d];

                if (map[backX][backY] == 1) {
                    // 벽이면 종료
                    System.out.println(getCleanArea());
                    return;
                } else {
                    // 벽 아니면 후진
                    setRobot(backX, backY, d, 0);
                }
            }

            // 1. 현재 위치 청소
            if (map[r][c] == 0)
                map[r][c] = 2;

            // 2. 현재 방향을 기준으로 왼쪽방향 확인
            int ld = (d + 3) % 4;
            int nx = r + dx[ld];
            int ny = c + dy[ld];

            // 3. 청소공간 있음 -> 한칸 전진 하고 1번으로
            // 4. 청소공간 없음 -> 그 방향으로 회전하고 2번으로
            if (map[nx][ny] == 0) {
                setRobot(nx, ny, ld, 0);
            } else {
                setRobot(r, c, ld, turnCount + 1);
            }
        }
    }

    // r, c, d, count 설정
    static void setRobot(int nextX, int nextY, int nextD, int nextCount) {
        r = nextX;
        c = nextY;
        d = nextD;
        turnCount = nextCount;
    }

    static int getCleanArea() {
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 2)
                    result++;
            }
        }
        return result;
    }
}



Python code

# -*- coding: utf-8 -*-
 
import sys
 
N = M = 0
arr = []
## 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
def countClean():
    count = 0
    for i in range(N):
        for j in range(M):
            if arr[i][j] > 1:
                count += 1
    return count
 
def leftTurn(d):
    if d == 0:
        return 3
    else:
        return d-1
 
def clean(x, y, d, turnCount):
    while True:
        ## 4방향 모두 탐색했으면 
        if turnCount == 4:
            backX = x - dx[d]
            backY = y - dy[d]
 
            if arr[backX][backY] == 1:
                print(countClean())
                return
            else:
                x, y, d, turnCount = backX, backY, d, 0
 
        ## 1. 현재 위치를 청소한다.
        if arr[x][y] == 0:
            arr[x][y] = 2
 
        ## 2. 왼쪽 방향부터 탐색
        ld = leftTurn(d)
        nx = x + dx[ld]
        ny = y + dy[ld]
 
        ## 왼쪽 방향에 청소 안함 (1) 1번부터 다시 시작
        if arr[nx][ny] == 0:
            x, y, d, turnCount = nx, ny, ld, 0
        else:
            ## 왼쪽 방향에 청소함 (2) 2번부터 시작
            ## 벽이면 왼쪽 탐색
            x, y, d, turnCount = x, y, ld, turnCount + 1
 
if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    r, c, d = map(int, sys.stdin.readline().split())
    visited = [[False]*M for i in range(N)]
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    clean(r, c, d, 0)


Problem


사과의 위치와 뱀의 이동 경로가 주어질 때 게임이 끝나는 초(second)를 구하는 문제입니다.



Solution

특별한 알고리즘은 사용하지 않고 문제에서 제시한 대로 구현만 하는 시뮬레이션 문제입니다.


조건을 살펴보면


  1. 뱀의 머리는 무조건 이동한다
  2. 뱀의 머리가 있는 곳에 사과가 있으면 꼬리 위치는 그대로
  3. 뱀의 머리가 있는 곳에 사과가 없으면 없으면 꼬리를 잘라낸다.
  4. 뱀의 머리가 있는 곳에 벽이나 뱀의 몸이 있다면 게임이 끝난다.


이렇게 총 4가지의 조건을 구현하면 됩니다.



오른쪽 왼쪽으로 방향을 바꾸는 건 % 연산자를 사용하면 쉽게 할 수 있습니다.


왼쪽으로 돌리기 = (현재 방향 + 3) % 4

오른쪽으로 돌리기 = (현재 방향 + 1) % 4


대신 처음 dxdy 배열을 북, 동, 남, 서 순서처럼 시계방향 또는 반시계 방향으로 설정해야 합니다.


인덱스가 0, 1, 2, 3 에서 반복된다는 점을 활용하면 % 4 연산자를 통해 다음 방향 인덱스를 쉽게 구할 수 있습니다.



뱀의 몸통을 기억하는 방법은 Deque 자료구조를 사용하였습니다.


Deque는 Queue나 Stack과 달리 리스트의 앞, 뒤에서 삽입/삭제가 가능한 자료구조입니다.


Deque 자체를 뱀의 몸이라고 생각하면서 꼬리를 삭제할때는 removeLast(), 머리를 이동시킬때는 addFirst()를 사용하면 됩니다.



Java Code

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

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static class Dot {
        int x, y;

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

    static int n;
    static int K;
    static int[][] map;
    static int L;
    static int[] time;
    static int[] dir;
    static int[] dx = {-1, 0, 1, 0};    // 북동남서
    static int[] dy = {0, 1, 0, -1};
    static Deque<Dot> snake = new ArrayDeque<Dot>();

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

        n = stoi(br.readLine());
        K = stoi(br.readLine());
        map = new int[n + 1][n + 1];    // 맨 위 맨 좌측은 (1,1)

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            int v1 = stoi(st.nextToken());
            int v2 = stoi(st.nextToken());
            map[v1][v2] = 1;    // 사과 위치는 1
        }

        L = stoi(br.readLine());
        time = new int[L];
        dir = new int[L];

        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());

            time[i] = stoi(st.nextToken());
            dir[i] = getDirection(st.nextToken());
        }

        // 문제 풀이
        solution();
    }

    static void solution() {
        int second = 0;
        int snakeDir = 1;    // 첫 방향은 오른쪽
        int timeIdx = 0;
        map[1][1] = 2;  // 처음 뱀의 위치는 (1,1)
        snake.add(new Dot(1, 1));

        while (true) {
            // 시간이 지나면 방향 바꾸기
            if (timeIdx < L && time[timeIdx] == second) {
                snakeDir = (snakeDir + dir[timeIdx]) % 4;
                timeIdx++;
            }

            // 1. 몸길이를 늘려 머리를 다음 칸에 위치시킨다
            int nx = snake.getFirst().x + dx[snakeDir];
            int ny = snake.getFirst().y + dy[snakeDir];

            // 몸이나 벽과 부딪히면 게임 끝
            if (nx <= 0 || nx > n || ny <= 0 || ny > n) {
                System.out.println(second + 1);
                break;
            }
            if (map[nx][ny] == 2) {
                System.out.println(second + 1);
                break;
            }

            if (map[nx][ny] == 1) {
                // 2. 만약 이동한 칸에 사과가 있다면, 사과 없어지고 꼬리 그대로 머리 추가
                map[nx][ny] = 2;
                snake.addFirst(new Dot(nx, ny));
            }
            else if (map[nx][ny] == 0) {
                // 3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여 꼬리가 위치한 칸 비우기
                map[nx][ny] = 2;
                snake.addFirst(new Dot(nx, ny));

                Dot tail = snake.removeLast();
                map[tail.x][tail.y] = 0;
            }

            second++;
        }
    }

    // 오른쪽은 1 왼쪽은 3
    static int getDirection(String s) {
        if (s.equals("D"))
            return 1;
        else
            return 3;
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import collections
 
N = 0
arr = []
## 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
snakes = collections.deque([[1,1]])
 
def printX():
    print()
    for i in range(1, N+1):
        for j in range(1, N+1):
            print(arr[i][j], end=" ")
        print()
 
 
def snake_move(direction):
    [x, y] = snakes[0]
    
    nx = x + dx[direction]
    ny = y + dy[direction]
 
    ## 머리가 몸통에 부딪히면 종료
    if [nx, ny] in snakes:
        return True
    
    ## 벽에 부딪히면 종료
    if nx <= 0 or nx > N or ny <= 0 or ny > N:
        return True
 
    ## 이동한 칸에 아무것도 없으면 꼬리를 줄여줌
    if arr[nx][ny] == 0:
        [ex, ey] = snakes.pop()
        arr[ex][ey] = 0
 
    ## 이동한 칸에 사과가 있으면 없애고 몸을 늘린다
    snakes.appendleft([nx, ny])
    arr[nx][ny] = 1
 
    return False
 
 
def rotate(s, d):
    ## L이면 왼쪽 D면 오른쪽
    if s == "L":
        return (d+3)%4
    else:
        return (d+1)%4
 
def solve(move, L):
    idx = 0
    direction = 1     ## 초기 방향은 오른쪽
    time = 0
 
    while True:
        if idx < L:
            if move[idx][0] == time:
                direction = rotate(move[idx][1], direction)
                idx += 1
 
        if snake_move(direction) == True:
            print(time+1)
            return
 
        time += 1
 
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    K = int(sys.stdin.readline())
    arr = [[0]*(N+1) for i in range(N+1)]
 
    for i in range(K):
        v1, v2 = map(int, sys.stdin.readline().split())
        arr[v1][v2] = 2
    
    L = int(sys.stdin.readline())
 
    move = []
    for i in range(L):
        X, C = sys.stdin.readline().split()
        move.append([int(X), C])
 
    ## 처음 뱀 위치
    arr[1][1] = 1
    solve(move, L)


Problem

벽 3개를 세운 뒤 바이러스를 퍼트렸을 때 가장 큰 안전 영역의 범위를 구하는 문제입니다.



Solution

문제를 보자마자 완전 탐색이라는 사실을 알 수 있습니다.


  1. 벽을 3개 세운다
  2. 바이러스를 퍼트린다.
  3. 안전 구역의 갯수를 센다.
  4. 제일 큰 값을 구한다.

이렇게 크게 4개의 순서로 이루어집니다.


백트래킹 을 통해서 벽 3개를 세울 수 있습니다.


n*m 개 중에서 3 개를 뽑는 Combination (조합) 을 구한다고 생각하면 됩니다.


기존에는 1차원 배열에서 구했던 조합을 2차원에서 구하는 것이 조금 어색할 수 있습니다.


숫자를 0 ~ n*m 까지 증가시킬때 (i/m, i%m) 을 좌표로 하면 2차원 배열의 모든 인덱스를 탐색할 수 있습니다.


예를 들어 n = 3, m = 2 인 3*2 배열을 탐색한다고 할 때


i(i/, i%m)좌표
0(0/2, 0%2)(0, 0)
1(1/2, 1%2)(0, 1)
2(2/2, 2%2)(1, 0)
3(3/2, 3%2)(1, 1)
4(4/2, 4%2)(2, 0)
5(5/2, 5%2)(2, 1)


이렇게 모든 좌표를 방문합니다.


파이썬은 i/m 을 구할 때 자동으로 실수형으로 바꿔주기 때문에 (int) i/m 으로 구하는 과정이 필요합니다.

추가) 파이썬은 // 연산자를 사용하면 정수형으로 리턴해준다고 합니다 (제보 감사합니다)


위의 규칙을 바탕으로 1차원 배열에서 조합을 구하듯이 해주시면 됩니다.


벽이 3개 세워진 후에는 맵을 복사합니다.


그리고 복사한 맵에 대해서 DFS를 통하여 바이러스를 퍼트립니다.


미리 값이 2인 좌표들을 따로 List에 저장하여 맵 전체를 스캔할 필요 없이 List만 순회하도록 합니다.


마지막으로 안전 구역을 구해서 MAX 값과 비교해서 갱신해주시면 됩니다.



Java Code

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

class Main {
    static class Dot {
        int x, y;

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

    static int n;
    static int m;
    static int[][] map;
    static int[][] copyed;
    static List<Dot> virusList = new ArrayList<Dot>();
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int max = 0;

    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];
        copyed = new int[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());
                if (map[i][j] == 2)
                    virusList.add(new Dot(i, j));
            }
        }

        setWall(0, 0);
        System.out.println(max);
    }

    // 백트래킹을 이용하여 3개의 벽 세우기
    static void setWall(int start, int depth) {
        if (depth == 3) {
            // 맵 복사
            copyMap();

            // 바이러스 퍼트리기
            for (Dot dot : virusList) {
                spreadVirus(dot.x, dot.y);
            }

            // 안전영역 크기 구하기
            max = Math.max(max, getSafeArea());
            return;
        }

        for (int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;

            if (map[x][y] == 0) {
                map[x][y] = 1;
                setWall(i + 1, depth + 1);
                map[x][y] = 0;
            }
        }
    }

    // 기존 맵을 유지하기 위해 바이러스 퍼트릴 맵 복사하기
    static void copyMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copyed[i][j] = map[i][j];
            }
        }
    }

    // DFS 로 바이러스 퍼트리기
    static void spreadVirus(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (copyed[nx][ny] == 0) {
                    copyed[nx][ny] = 2;
                    spreadVirus(nx, ny);
                }
            }
        }
    }

    static int getSafeArea() {
        int safe = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyed[i][j] == 0)
                    safe++;
            }
        }
        return safe;
    }
}



Python Code

# -*- coding: utf-8 -*- import copy import sys n = m = 0 arr = [] virusList = [] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] maxVal = 0 ## 안전구역 넓이 구하기 def getSafeArea(copyed): safe = 0 for i in range(n): for j in range(m): if copyed[i][j] == 0: safe += 1 return safe ## DFS로 바이러스 퍼트리기 def spraedVirus(x, y, copyed): for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx and nx < n and 0 <= ny and ny < m: if copyed[nx][ny] == 0: copyed[nx][ny] = 2 spraedVirus(nx, ny, copyed) ## 조합으로 벽 3개 놓는 모든 경우 구하기 def setWall(start, depth): global maxVal if depth == 3: # 복사 copyed = copy.deepcopy(arr) length = len(virusList) for i in range(length): [virusX, virusY] = virusList[i] spraedVirus(virusX, virusY, copyed) maxVal = max(maxVal, getSafeArea(copyed)) return for i in range(start, n*m): x = i // m y = i % m if arr[x][y] == 0: arr[x][y] = 1 setWall(i + 1, depth + 1) arr[x][y] = 0 if __name__ == '__main__': n, m = map(int, sys.stdin.readline().split()) for i in range(n): arr.append(list(map(int, sys.stdin.readline().split()))) for i in range(n): for j in range(m): if arr[i][j] == 2: virusList.append([i, j]) ## 벽세우기 setWall(0, 0) print(maxVal)


문제 링크 : https://www.acmicpc.net/problem/1005


건물의 빌드 순서를 정해줄 때 특정 건물을 짓기 위해 총 소요되는 시간을 구하는 문제입니다.


DFS로 해당 건물에 도달하기 위한 모든 경우를 탐색하는 방법도 있지만


방향을 갖고 사이클이 없다는 DAG 특성을 이용하여 위상 정렬을 사용하였습니다.


위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21


일반적인 위상정렬과 다른 점은 노드의 순서가 아니라 소요 시간을 기억해야한다는 점입니다.


result 배열을 따로 만들어서 총 소요시간을 저장해둡니다.


1. 처음 indegree 가 0 인 건물들은 이전 테크가 없기 때문에 총 소요시간이 d[i] 입니다.

2. Queue에서 건물을 빼면서 해당 건물과 연결된 다른 건물들의 result 를 갱신해줍니다.

3. 이전까지의 소요시간 result[node] + 현재 건물의 소요시간 d[i] 로 이루어지며 이전 테크가 전부 올라가야 현재 건물을 지을 수 있기 때문에 가장 오래 걸리는 시간으로 갱신해줍니다.


문제 링크 : https://www.acmicpc.net/problem/1766


문제를 푸는 순서를 정해야 합니다.


문제를 효율적으로 풀기 위해서 선수 문제가 필요한 문제는 무조건 순서에 맞춰서 풉니다.


이 문제는 위상 정렬을 사용하면 쉽게 해결할 수 있습니다.


위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21


한가지 다른 점은 원래 위상 정렬은 결과값이 하나가 아닙니다.


간선에 따라서 여러 결과가 나오기도 하는데 이 문제는 무조건 숫자가 낮은 문제를 먼저 풀어야 한다고 딱 정했습니다.


그래서 위상 정렬을 구현할 때 일반 큐 대신에 우선순위 큐(PriorityQueue)를 사용합니다.


문제 링크 : https://www.acmicpc.net/problem/2252


위상 정렬 문제입니다.


위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21


노드 갯수 N, 간선 갯수 M 을 받은 다음에 간선의 가중치를 입력받아서 위상 정렬하면 간단하게 해결됩니다.


result 큐를 사용해서 결과값을 저장했지만 q 에 대한 while 문이 도는 동안 그대로 출력해도 상관없습니다.


위상정렬


위상 정렬은 그래프 정렬을 말합니다.


그래프의 순서를 정렬하기 때문에 조건이 있습니다.


위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 합니다.


  1. 말 그래도 두 노드 A, B 사이에 A -> B 같은 관계가 성립되어야 하며
  2. A -> B, B <- A 처럼 그래프들 사이에 사이클이 없어야 합니다.


위상정렬은 DFS를 사용하여 구현하거나 indegree 배열을 사용하여 구현 할 수 있습니다.


가장 주로 쓰이고 간단한 indegree 구현에 대해서 알아보겠습니다.



변수설명
List<List<Integer>> array그래프의 관계를 표현하기 위한 2차원 인접 리스트
int[] indegree해당 노드를 가리키는 간선 갯수를 담기 위한 배열
Queue<Integer> qindegree 값이 0 이 된 노드들을 담기 위한 Queue
Queue<Integer> resultQueue 에서 꺼내져 결과로 출력하기 위해 담는 결과 Queue



간단하게 그래프를 만들어보았습니다.


동그라미 안에 있는 숫자는 노드의 번호이며, 조그만 네모 안에 있는 숫자들은 자신을 가리키는 간선들의 갯수인 indegree 값입니다.



  1. 맨 처음 indegree 가 0 인 값들을 Queue 에 담고 시작합니다.

1



  1. Queue 에서 1을 빼주며 노드 1 에게 가리켜지는 다른 노드들의 indegree 값을 1 씩 감소시킵니다.


    사용한 노드와 간선은 지운다고 생각하면 이해하기 쉽습니다.


    아래 그림에서 화살표를 지우고 생각해보면 노드 2 와 노드 3은 자신을 가리키는 간선이 0 인 것을 알 수 있습니다.

2



  1. 그다음은 Queue 에서 순서대로 노드 2를 꺼냅니다.


    역시 노드 2와 연결된 간선들을 지우며 연결되어있는 노드들의 indegree 값을 감소시킵니다.


    노드 5 의 indegree 값이 0 이 되었으므로 Queue 에 넣어줍니다.

    Queue 가 전부 비워질 때까지 같은 과정을 반복하면 됩니다.

3



  1. Queue.pop(3) && Result.add(3)

4



  1. Queue.pop(5) && Result.add(5)

5



  1. Queue.pop(7) && Result.add(7)

6



  1. Queue.pop(4) && Result.add(4)

7



  1. Queue.pop(6) && Result.add(6)

8



이렇게 Queue가 비워지고 Result에 들어있는 값이 위상 정렬된 결과값입니다.


순서가 저렇게 나왔지만 사실 위상 정렬은 정해진 결과값이 없습니다.


2와 3의 위치가 바뀌어도 성립합니다.


중요한 점은 화살표가 가리키는 순서는 꼭 지켜져야 한다는 겁니다.


1 - 2 - 5 - 4 - 6
1 - 2 - 4 - 6
1 - 3 - 4 - 6
1 - 3 - 7


이 순서는 어떤 정렬 결과가 나오더라도 변하지 않을겁니다.



Java Code

import java.util.*;

public class TopologicalSort {
    static int n;
    static int e;

    public static void main(String[] args) {
        n = 7; // 정점 갯수
        e = 9; // 간선 갯수
        int[] indegree = new int[n + 1];
        List<List<Integer>> array = new ArrayList<List<Integer>>();

        for (int i = 0; i < n + 1; i++)
            array.add(new ArrayList<Integer>());

        // 간선 목록 v1 -> v2
        int[] v1 = {1, 1, 2, 4, 3, 3, 5, 2, 5};
        int[] v2 = {2, 3, 5, 6, 4, 7, 6, 4, 4};

        /**
         * 1. v1 -> v2 인접리스트 생성
         * 2. v2 를 가리키는 노드 갯수 indegree 증가
         */
        for (int i = 0; i < e; i++) {
            int c1 = v1[i];
            int c2 = v2[i];

            array.get(c1).add(c2);
            indegree[c2]++;
        }

        topologicalSort(indegree, array);
    }

    static void topologicalSort(int[] indegree, List<List<Integer>> array) {
        Queue<Integer> q = new LinkedList<Integer>();
        Queue<Integer> result = new LinkedList<Integer>();

        // 큐에 indegree 가 0 인 노드 담기
        for (int i = 1; i < n + 1; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        /**
         * 1. 큐에서 값을 꺼내며 해당 노드가 가리키는 노드의 indegree 를 1 감소
         * 2. 만약 indegree가 0 이 된다면 큐에 넣기
         * 3. 큐가 빌때까지 반복
         */
        while (!q.isEmpty()) {
            int node = q.poll();
            result.offer(node);

            for (Integer i : array.get(node)) {
                indegree[i]--;

                if (indegree[i] == 0) {
                    q.offer(i);
                }
            }
        }

        System.out.println(result);
    }
}


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
부분집합 PowerSet (Java)  (2) 2018.12.27
조합 Combination (Java)  (7) 2018.12.27
순열 Permutation (Java)  (11) 2018.12.27

Problem


종이 위에 테트로미노 블록을 하나 놓아서 각 칸에 놓인 숫자 합의 최대값을 구하는 문제입니다.



Solution

테트로미노 블록에 들어있는 모든 숫자를 더한 값 중 최대값을 찾는 문제입니다.


DFS 로 깊이 4 까지 탐색하면 간단하게 풀 수 있습니다.


대신 블록 중에 ㅗ 모양은 DFS 돌려도 나오지 않으므로 따로 예외처리를 해주시면 됩니다.


  1. 맵의 꼭지점일 때
  2. 맵의 테두리일때
  3. 일반적일 때


이렇게 세 가지 경우로 나누어서 각각 하드코딩 해주었습니다.



Java Code

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

class Main {
    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static int max = 0;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        n = stoi(st.nextToken());
        m = stoi(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] = stoi(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = true;
                dfs(i, j, 0, 0);
                visited[i][j] = false;
                another(i, j);
            }
        }

        System.out.println(max);
    }

    // dfs로 깊이가 최대 4인 경우가 테트로미노, 단 ㅗ 모양은 없음
    static void dfs(int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (visited[nx][ny] != true) {
                    visited[nx][ny] = true;
                    dfs(nx, ny, depth + 1, sum + map[nx][ny]);
                    visited[nx][ny] = false;
                }
            }
        }
    }

    // ㅗ 모양을 찾는다. 가운데 있는 좌표를 기준으로 세 방향을 탐색한다.
    static void another(int x, int y) {
        // 1. 맵의 꼭지점일때는 ㅗ 모양 불가능
        if ((x == 0 || x == n - 1) && (y == 0 || y == m - 1)) return;

        int sum = map[x][y];

        // 2. 맵의 테두리일때는 모양이 하나
        if (x == 0)
            sum += map[x][y - 1] + map[x][y + 1] + map[x + 1][y];
        else if (x == n - 1)
            sum += map[x][y - 1] + map[x][y + 1] + map[x - 1][y];
        else if (y == 0)
            sum += map[x - 1][y] + map[x + 1][y] + map[x][y + 1];
        else if (y == m - 1)
            sum += map[x - 1][y] + map[x + 1][y] + map[x][y - 1];
        else {
        // 3. 맵의 테두리가 아닐 때는 4 개의 모양을 비교
            sum = Math.max(sum, map[x][y] + map[x + 1][y] + map[x][y - 1] + map[x][y + 1]);
            sum = Math.max(sum, map[x][y] + map[x - 1][y] + map[x][y - 1] + map[x][y + 1]);
            sum = Math.max(sum, map[x][y] + map[x][y + 1] + map[x - 1][y] + map[x + 1][y]);
            sum = Math.max(sum, map[x][y] + map[x][y - 1] + map[x - 1][y] + map[x + 1][y]);
        }

        max = Math.max(max, sum);
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
 
n = m = 0
arr = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
maxVal = 0
 
## 최대 4개짜리 dfs로 전부 탐색하면됨
def dfs(x, y, visited, count, sumVal):
    global maxVal
 
    if count == 4:
        if maxVal < sumVal:
            maxVal = sumVal
        return
 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
 
        if 0 <= nx and nx < n and 0 <= ny and ny < m:
            if visited[nx][ny] == False:
                visited[nx][ny] = True
                dfs(nx, ny, visited, count + 1, sumVal + arr[nx][ny])
                visited[nx][ny] = False
        
## ㅗ 모양은 dfs로 탐색이 안돼서 따로 처리해줌
## 가운데일 때를 기준으로 네방향 탐색
def fuck(x, y):
    global maxVal
    sumVal = arr[x][y]
    
    ## x, y가 모서리면 ㅗ 모양은 아예 불가능
    if x == 0:
        if y == 0 or y == m-1:
            return
    elif x == n-1:
        if y == 0 or y == m-1:
            return
 
    ## x나 y가 가장자리에 있으면 ㅗ 모양은 하나밖에 안나옴
    if x == 0:
        sumVal += arr[x+1][y] + arr[x][y-1] + arr[x][y+1]
    elif x == n-1: 
        sumVal += arr[x-1][y] + arr[x][y-1] + arr[x][y+1]    
    elif y == 0:
        sumVal += arr[x][y+1] + arr[x-1][y] + arr[x+1][y]    
    elif y == m-1:
        sumVal += arr[x][y-1] + arr[x-1][y] + arr[x+1][y]
    else:  
        sumlist = []
        sumlist.append(sumVal + arr[x+1][y] + arr[x][y-1] + arr[x][y+1])
        sumlist.append(sumVal + arr[x-1][y] + arr[x][y-1] + arr[x][y+1])
        sumlist.append(sumVal + arr[x][y+1] + arr[x-1][y] + arr[x+1][y])
        sumlist.append(sumVal + arr[x][y-1] + arr[x-1][y] + arr[x+1][y])
        sumVal = max(sumlist)
    
    if maxVal < sumVal:
        maxVal = sumVal
 
def solve():
    visited = [[False]*m for i in range(n)]
 
    for i in range(n):
        for j in range(m):
            fuck(i, j)
            visited[i][j] = True
            dfs(i, j, visited, 1, arr[i][j])
            visited[i][j] = False
 
 
if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
 
    for i in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))
        
    solve()
    print(maxVal)


+ Recent posts