Problem


톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하여


접수의 합을 출력하는 문제입니다.



Solution

특별한 알고리즘은 없이 톱니의 상태에 맞추어 톱니바퀴를 회전시키는 단순 구현 시뮬레이션 문제입니다.


이 문제에서 주의해야 할 점은 두 가지 입니다.


  1. 좌, 우 톱니바퀴의 회전 여부는 회전이 이루어지기 전에 결정된다.
  2. 톱니바퀴의 번호는 0 ~ 3 이 아니라 1 ~ 4 다.


1 번은 말그대로 톱니바퀴를 회전시키기 전에 모든 톱니바퀴에 대해서 회전 여부가 결정되어야 합니다.


저는 재귀를 통해 현재 상태에서 N 극과 S 극을 비교하여 회전 여부를 결정하고


가장 끝에있는 1 번 또는 4 번 부터 회전시켰습니다.


2 번은 사소한 실수인데 보통 톱니바퀴를 배열로 선언하다보니 0 ~ 3 이라고 착각하는 경우가 있습니다.


구현하는 함수는 톱니바퀴를 회전시키는 rotate 함수와


좌, 우 톱니바퀴 회전 여부를 판단하기 위한 leftright 함수입니다.


톱니바퀴를 회전시키는 건 for 문을 사용하면 됩니다.


leftright 함수는 재귀를 통하여 모든 톱니바퀴의 회전 여부를 검사합니다.


톱니바퀴의 번호가 0 ~ 3 이라고 생각하고 2 번을 회전시키라는 명령이 들어오면 다음과 같은 로직으로 진행됩니다.


example


회전 여부를 확인하기 위해 호출되는 것이 leftright 함수고 시간 순서대로 화살표를 따라서 진행됩니다.


코드를 보시면 쉽게 이해하실 수 있습니다.


파이썬은 deque 를 자료구조를 사용하였고 deque 에 있는 rotate 함수를 사용하였습니다.



Java Code

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

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

    // 톱니바퀴 [번호][방향]
    static int[][] arr = new int[4][8];

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

        for (int i = 0; i < 4; i++) {
            String s = br.readLine();
            for (int j = 0; j < 8; j++) {
                arr[i][j] = s.charAt(j) - '0';
            }
        }

        int k = stoi(br.readLine());

        // 톱니바퀴 회전
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = stoi(st.nextToken());
            int dir = stoi(st.nextToken());

            // 톱니바퀴 번호는 1~4, 인덱스는 0~3
            solution(idx - 1, dir);
        }

        // 점수 계산
        int score = 0;
        for (int i = 0; i < 4; i++) {
            score += arr[i][0] * (1 << i);
        }

        System.out.println(score);
    }

    // 9시 방향은 2, 3시 방향은 6
    static void solution(int idx, int dir) {
        left(idx - 1, -dir);
        right(idx + 1, -dir);
        rotate(idx, dir);
    }

    // 왼쪽에 있던 톱니바퀴 회전 여부 결정
    static void left(int idx, int dir) {
        if (idx < 0) return;

        if (arr[idx][2] != arr[idx + 1][6]) {
            left(idx - 1, -dir);
            rotate(idx, dir);
        }
    }

    // 오른쪽에 있던 톱니바퀴 회전 여부 결정
    static void right(int idx, int dir) {
        if (idx > 3) return;

        if (arr[idx][6] != arr[idx - 1][2]) {
            right(idx + 1, -dir);
            rotate(idx, dir);
        }
    }

    // dir = 1 시계방향, dir = -1 반시계방향
    static void rotate(int idx, int dir) {
        if (dir == 1) {
            int temp = arr[idx][7];

            for (int i = 7; i > 0; i--) {
                arr[idx][i] = arr[idx][i - 1];
            }

            arr[idx][0] = temp;

        } else {
            int temp = arr[idx][0];

            for (int i = 0; i < 7; i++) {
                arr[idx][i] = arr[idx][i + 1];
            }

            arr[idx][7] = temp;
        }
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import collections
 
wheels = []
turns = []
 
def turnLeft(i, d):
    if i < 0:
        return
 
    if wheels[i][2] != wheels[i+1][6]:
        turnLeft(i-1, -d)
        wheels[i].rotate(d)
 
def turnRight(i, d):
    if i > 3:
        return
 
    if wheels[i][6] != wheels[i-1][2]:
        turnRight(i+1, -d)
        wheels[i].rotate(d)
 
def solve():
    for turn in turns:
        [idx, direction] = turn
        
        turnLeft(idx-1, -direction)
        turnRight(idx+1, -direction)
 
        wheels[idx].rotate(direction)
 
if __name__ == '__main__':
    for i in range(4):
        wheels.append(collections.deque(list(sys.stdin.readline())[:8]))
 
    K = int(sys.stdin.readline())
 
    for i in range(K):
        v1, v2 = map(int, sys.stdin.readline().split())
        turns.append([v1-1, v2])
 
    solve()
    sumVal = 0
    for i, wheel in enumerate(wheels):
        sumVal += int(wheel[0]) * (1 << i)
    print(sumVal)


Problem


지도의 크기와 높이가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 문제입니다.



Solution

문제 특성상 코드가 굉장히 지저분하게 나올 수밖에 없다고 생각합니다.


우선 이 길이 맞는지 확인하는 canGo(x, y, d) 메소드를 만들었습니다.


시작 x, 시작 y, 그리고 가로 세로 여부를 판단하는 d 를 파라미터로 받습니다.


2차원으로 되어 있는 지도에서 길 하나만을 체크하는 것이기 때문에 height 라는 1차원 배열에 옮겨담았습니다.


그리고 visited 배열을 사용하였는데, 경사로를 중복으로 놓는 상황을 방지하기 위해서 만들었습니다.


height 배열을 1 ~ n-1 까지 돌면서 확인합니다.


  1. 높이가 같으면 패스
  2. 높이 차이가 2 이상이면 false
  3. 내려가야 되는 경우
  4. 올라가야 되는 경우


이렇게 4가지 경우를 만들어서 예외처리를 하였습니다.


내려가야 하는 경우는 다음 인덱스부터 앞으로 길이 L 만큼


올라가야 하는 경우는 현재 인덱스부터 뒤로 길이 L 만큼


경사로를 놓을 땅이 있는지 확인합니다.


  1. 경사로 놓는 범위가 지도를 벗어나거나 j >= n
  2. 경사로 놓는 땅의 높이가 다르거나 height[i+1] != height[j] or height[i] != height[j]
  3. 이미 다른 경사로가 놓여있는 경우 visited[j] == true


위 세가지 경우 중에 하나라도 만족하면 false 를 return 합니다.


만약 위에 세 조건에 걸리지 않고 무사히 for 문을 돌면 끝까지 도착했다는 뜻이므로 true 를 return 합니다.


x 가 0 이며 세로로 가는 길 또는 y 가 0 이며 가로로 가는 길 모두 확인하며 카운트를 해준 뒤에 출력해주면 됩니다.



Java Code

import java.io.*;
import java.util.*;
 
class Main {
    static int stoi(String s) { return Integer.parseInt(s); }
 
    static int n;
    static int L;
    static int[][] map;
    static int count = 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());
        L = stoi(st.nextToken());
        map = new int[n][n];
 
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++)
                map[i][j] = stoi(st.nextToken());
        }
 
        // 풀이 시작
        for (int i=0; i<n; i++) {
            if (canGo(i, 0, 0)) 
                count++;
            
            if (canGo(0, i, 1)) 
                count++;
        }
 
        System.out.println(count);
    }
 
    // 한 줄이 경사로인지 확인 d = 0 이면 행검사, d = 1 이면 열검사
    static boolean canGo(int x, int y, int d) {
        int[] height = new int[n];
        boolean[] visited = new boolean[n];     // 경사로가 이미 놓여있는지 체크
 
        // 알아보기 쉽게 height 배열에 옮기기
        for (int i=0; i<n; i++) {
            height[i] = (d == 0) ? map[x][y+i] : map[x+i][y];
        }
 
        for (int i=0; i<n-1; i++) {
            // 높이가 같으면 패스
            if (height[i] == height[i+1]) {
                continue;
            }
            
            if (Math.abs(height[i] - height[i+1]) > 1) {
                return false;
            }
 
            // 내려가야되는 경우
            if (height[i] - 1 == height[i+1]) {
                for (int j=i+1; j<=i+L; j++) {
                    // j가 범위를 벗어나거나 높이가 다르거나 이미 경사로가 있는 경우
                    if (j >= n || height[i+1] != height[j] || visited[j] == true) {
                        return false;
                    } 
                    visited[j] = true;
                }
            }
            // 올라가야되는 경우
            else if (height[i] + 1 == height[i+1]) {
                for (int j=i; j>i-L; j--) {
                    if (j < 0 || height[i] != height[j] || visited[j] == true) {
                        return false;
                    }
                    visited[j] = true;
                }
            }            
        }
 
        return true;
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import itertools
 
N = L = 0
arr = []
 
def canGoPath(heights):
    current = heights[0]
    visited = [False for i in range(N)]
 
    for i, height in enumerate(heights):
        ## 높이가 똑같으면 그냥 진행
        if current == height:
            continue
 
        ## 높은 곳으로 이동
        ## 지금까지 이동한 거리가 L보다 크거나 같으면 이동가능
        elif current + 1 == height:
            for j in range(i-1, i-1-L, -1):
                if j < 0 or current != heights[j] or visited[j] == True:
                    return False
                visited[j] = True
            current = height
 
        ## 낮은 곳으로 이동
        ## 앞으로 이동할 곳에서 L만큼 같은 거리가 있으면 가능
        elif current - 1 == height:
            for j in range(i, i+L):
                if j >= N or current - 1 != heights[j] or visited[j] == True:
                    return False
                visited[j] = True
            current = height
        
        ## 높이 차이가 1 이상이면 불가능
        else:
            return False
    
    return True
 
 
def solve():
    count = 0
    for i in range(N):
        if canGoPath(arr[i]):
            count += 1
 
    for j in range(N):
        path = []
        for i in range(N):
            path.append(arr[i][j])
        
        if canGoPath(path):
            count += 1
    
    print(count)
 
if __name__ == '__main__':
    N, L = map(int, sys.stdin.readline().split())
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    solve()


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


Solution

주어진 N 명의 사람들을 두 팀으로 나눈 뒤에 능력치의 차이가 최소가 되는 값을 구하는 문제입니다.


N 명 중에서 N/2 명 뽑아야 하기 때문에 조합(Combination) 을 사용하였습니다.


조합에 대한 포스팅 https://bcp0109.tistory.com/15


스타트팀은 visited 값을 true, 링크 팀은 visited 값을 false 로 하여 각 팀의 능력치 합을 따로 구해서 최소값을 찾아주시면 됩니다.


** 주의사항 1.


능력치의 차를 구해야 하기 때문에 절대값으로 계산해야합니다. Math.abs 함수를 사용해줍시다.


** 주의사항 2.


2 명이 팀일때는 예시에 나온대로


(2, 1) + (1, 2)

(3, 4) + (4, 3)


이렇게 각 팀의 능력치를 구할수 있습니다.


3 명이 팀일때는


(1, 2) + (2, 1) + (1, 3) + (3, 1) + (2, 3) + (3, 2)

(4, 5) + (5, 4) + (4, 6) + (6, 4) + (5, 6) + (6, 5)


이렇게 각 팀의 능력치의 합을 구해야 합니다.



Java Code


import java.util.*;
import java.io.*;
 
// https://www.acmicpc.net/problem/14889
 
class Main {
    static int stoi(String s) { return Integer.parseInt(s); }
 
    static int n;
    static boolean[] visited;
    static int[][] arr;
    static int min = 987654321;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        n = stoi(br.readLine());
        visited = new boolean[n+1];
        arr = new int[n+1][n+1];
 
        for(int i=1; i<n+1; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<n+1; j++) {
                arr[i][j] = stoi(st.nextToken());
            }
        }
 
        comb(10);
        System.out.println(min);
    }
 
    // 모든 팀의 조합 구하기
    static void comb(int startint depth) {
        if(depth == n/2) {
            min = Math.min(min, getAbilityDifference());
            return;
        }
 
        for(int i=start; i<n+1; i++) {
            if(visited[i] != true) {
                visited[i] = true;
                comb(i+1, depth+1);
                visited[i] = false;
            }
        }
    }
 
    // 팀의 능력치 차이를 구하기
    static int getAbilityDifference() {
        int sumStart = 0;
        int sumLink = 0;
 
        for(int i=1; i<n+1; i++) {
            for(int j=1; j<n+1; j++) {
                // true 면 스타트팀
                if(visited[i] && visited[j])
                    sumStart += arr[i][j];
 
                // false 면 링크팀
                if(visited[i] != true && visited[j] != true)
                    sumLink += arr[i][j];
            }
        }
 
        return Math.abs(sumStart - sumLink);
    }
}


Python Code


# -*- coding: utf-8 -*-
 
import sys
import itertools
 
= 0
arr = []
 
def team(member):
    allMember = [for i in range(N)]
    start_team = []
    link_team = []
 
    ## 멤버 선택
    for i in allMember:
        if i in member:
            start_team.append(i)
        else:
            link_team.append(i)
 
    start_sum = 0
    for i in start_team:
        for j in start_team:
            start_sum += arr[i][j]
    
    link_sum = 0
    for i in link_team:
        for j in link_team:
            link_sum += arr[i][j]
 
    return abs(start_sum - link_sum)
 
def solve(members):
    ## 모든 경우의 수 뽑기
    combination_members = itertools.combinations(members, int(N/2))
    selected_members = list(combination_members)
    length = int(len(selected_members)/2)
 
    minVal = sys.maxsize
    for member in selected_members[:length]:
        minus = team(member)
 
        if minVal > minus:
            minVal = minus
    
    print(minVal)
 
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    members = [for i in range(N)]
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    solve(members)
    


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)


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)


Problem


수열과 연산자가 주어졌을 때 조합하여 만들수 있는 최소값과 최대값을 구하는 문제입니다.



Solution

연산자가 배치될 수 있는 모든 경우의 수를 구한 후에 MAXMIN 값을 구하는 문제입니다.


단순하게 재귀로 풀수도 있지만 순열을 이용하여 풀었습니다.


모든 경우의 수를 봐야 하고 순서는 중요하지 않기 때문에 간단하게 swap 으로 순열을 구현하였습니다.


  1. operator 배열을 만들어서 각 연산자 갯수에 대해 1, 2, 3, 4로 넣기
  2. operator 배열에 대해서 순열 돌리기
  3. 순열로 인한 경우의 수 마다 연산값을 계산하여 maxmin 값 구하기
  4. 출력


위와 같은 순서로 진행하였습니다.


파이썬은 좀더 예전에 풀었던 거라 연산자를 아예 +, -, *, / 로 배열에 저장했는데 순열을 구한 뒤 계산한다는 전체적인 로직은 같습니다.



Java Code

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

class Main {
    static int n;
    static int[] a;
    static int[] operator;
    static int max = -987654321;
    static int min = 987654321;

    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;

        n = stoi(br.readLine());
        a = new int[n];
        operator = new int[n - 1];

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

        st = new StringTokenizer(br.readLine());
        int idx = 0;
        for (int i = 0; i < 4; i++) {
            int temp = stoi(st.nextToken());

            // 1:덧셈, 2:뺄셈, 3:곱셈, 4:나눗셈
            for (int j = 0; j < temp; j++) {
                if (i == 0) operator[idx++] = 1;
                else if (i == 1) operator[idx++] = 2;
                else if (i == 2) operator[idx++] = 3;
                else operator[idx++] = 4;
            }
        }

        // 계산 시작
        permutation(0);
        System.out.println(max);
        System.out.println(min);
    }

    // 순열 구하기
    static void permutation(int depth) {
        if (depth == n - 1) {
            calculate();
            return;
        }

        for (int i = depth; i < n - 1; i++) {
            swap(depth, i);
            permutation(depth + 1);
            swap(depth, i);
        }
    }

    static void swap(int i, int j) {
        int temp = operator[i];
        operator[i] = operator[j];
        operator[j] = temp;
    }

    // 각 순열에 대해서 연산 후 max, min 값 찾기
    static void calculate() {
        int result = a[0];

        for (int i = 0; i < n - 1; i++) {
            if (operator[i] == 1) result += a[i + 1];
            else if (operator[i] == 2) result -= a[i + 1];
            else if (operator[i] == 3) result *= a[i + 1];
            else result /= a[i + 1];
        }

        min = Math.min(min, result);
        max = Math.max(max, result);
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import itertools
 
def setOperatorList(N, add, sub, mul, div):
    operator = []
 
    for i in range(N-1):
        if add > 0:
            operator.append("+")
            add -= 1
        elif sub > 0:
            operator.append("-")
            sub -= 1
        elif mul > 0:
            operator.append("*")
            mul -= 1
        elif div > 0:
            operator.append("/")
            div -= 1
 
    return operator
 
 
def solve(N, A, operator):
    result = A[0]
 
    for i in range(N-1):
        if operator[i] == "+":
            result = result + A[i+1]
        elif operator[i] == "-":
            result = result - A[i+1]
        elif operator[i] == "*":
            result = result * A[i+1]
        elif operator[i] == "/":
            result = int(result / A[i+1])
 
    return result
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    A = [i for i in list(map(int, sys.stdin.readline().split()))]
    add, sub, mul, div = map(int, sys.stdin.readline().split())
    
    operatorList = setOperatorList(N, add, sub, mul, div)
 
    operators = itertools.permutations(operatorList)
 
    maxVal = -sys.maxsize
    minVal = sys.maxsize
 
    for operator in operators:
        result = solve(N, A, operator)
 
        if result < minVal:
            minVal = result
        
        if result > maxVal:
            maxVal = result
 
    print(maxVal)
    print(minVal)


+ Recent posts