방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 구현 문제로 문제에서 요구하는 바를 그대로 코드로 작성하면 해결할 수 있는 문제였습니다. 

과정은 다음과 같습니다.

1. 로봇과 벨트를 함께 이동

2. 먼저 올린 순서대로 로봇 이동(먼저 올린 순서는 n-1번째부터 0번째까지 역순으로 이동하면 쉽게 해결 가능)

3. 로봇을 0번째에 올리기

4. 내구도가 0인 벨트의 수가 K 이상인지 확인하기.

단, 이때 2번, 3번 과정은 해당하는 벨트의 내구도가 1 감소한다는 것 그리고 1번, 2번 과정은 n-1번째에서 로봇이 내린다는 것을 적용하면 해결할 수 있습니다.

소스코드

n, k = map(int, input().split())
arr = list(map(int, input().split()))
robotInfo = []

ans = 0
for i in range(len(arr)):
  robotInfo.append((arr[i], ''))
  
while True:
  ans += 1
  # 1단계
  temp, robot = robotInfo[2*n-1]
  for i in range(2*n-1, 0, -1):
    robotInfo[i] = robotInfo[i-1]
  robotInfo[0] = (temp, robot)
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")

  # 2단계
  for i in range(n-1, -1, -1):
    temp, robot = robotInfo[i]
    if robot != "":
      nextTemp, nextRobot = robotInfo[i + 1]
      if nextTemp >= 1 and nextRobot == "":
        robotInfo[i] = (temp, "")
        robotInfo[i + 1] = (nextTemp-1, "exist")
  temp, robot = robotInfo[n-1]
  robotInfo[n-1] = (temp, "")
  
  # 3단계
  temp, robot = robotInfo[0]
  if temp >= 1:
    robotInfo[0] = (temp-1, "exist")

  # 4단계
  cnt = 0
  for i in range(0, 2*n):
    temp, robot = robotInfo[i]
    if temp == 0:
      cnt += 1
  if cnt >= k:
    break
print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 역시 마찬가지로 구현 문제이므로 차분하게 조건을 작성하면 해결할 수 있었다. 돌리게 되는 톱니를 기준으로 좌측 영역, 우측 영역을 분리하여 각자 맞게 회전을 시켜주었다. 다만 이때 flagLeft(왼쪽에 맞물리는 부분) flagRight(우측에 맞물리는 부분)을 for문 내부에 그대로 넣어서 덮어진 값을 사용하게 되어 틀렸습니다. 를 받게 되었다. 따라서 tempFlagLeft, tempFlagRight로 분리하여 덮어씌워짐을 방지 하였다.

소스코드

arr = [[] for _ in range(4)]
for i in range(4):
   tempArr = input()
   for j in range(len(tempArr)):
       arr[i].append(int(tempArr[j]))
k = int(input())
moves = []
for _ in range(k):
    a, b = map(int, input().split())
    moves.append((a, b))

def turn_right(array):
    right = array[7]
    for i in range(6, -1, -1):
        array[i + 1] = array[i]
    array[0] = right

def turn_left(array):
    left = array[0]
    for i in range(0, 7):
        array[i] = array[i + 1]
    array[7] = left

for x in range(k):
    num, dir = moves[x]
    num -= 1 # index 맞추기 위함
    flagLeft = arr[num][6]
    flagRight = arr[num][2]
    if dir == 1:
        turn_right(arr[num])
    else:
        turn_left(arr[num])
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num-1, -1, -1):
        if tempFlagLeft != arr[i][2]:
            if tempDir == 1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
        else:
            break
    tempDir = dir
    tempFlagLeft = flagLeft
    tempFlagRight = flagRight
    for i in range(num + 1, 4):
        if tempFlagRight != arr[i][6]:
            if tempDir == -1:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_right(arr[i])
                tempDir *= -1
            else:
                tempFlagLeft = arr[i][6]
                tempFlagRight = arr[i][2]
                turn_left(arr[i])
                tempDir *= -1
        else:
            break

ans = 0
for i in range(len(arr)):
    if arr[i][0] == 1:
        if i == 0:
            ans += 1
        elif i == 1:
            ans += 2
        elif i == 2:
            ans += 4
        else:
            ans += 8
print(ans)

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

문제 해결을 위한 과정

구현 유형에 해당하는 문제 입니다. 조건 자체는 복잡할 수 있으나, 조건에 유의하여 소스코드를 작성하면 해결할 수 있었습니다. (저의 경우 possible.append()를 graph[nx][ny] == 0 즉 비어있을 때만 해줘야하는데 실수로 그렇지 않은 경우에도 append할 수 있게 작성하여 여러번 시도하여 해결했습니다.)

소스코드

a = int(input())
n = a * a
graph = [[0] * a for _ in range(a)]
friend = []
happy = [0, 1, 10, 100, 1000]
for _ in range(n):
  friend.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(len(friend)):
  main = friend[i][0]
  bestFriend = friend[i][1:5]
  possible = []
  
  for j in range(a):
    for k in range(a):
      cnt = 0
      emptyCnt = 0
      if graph[j][k] == 0:
        for l in range(4):
          nj = j + dx[l]
          nk = k + dy[l]
          if nj < 0 or nk < 0 or nj >= a or nk >= a:
            continue
          if graph[nj][nk] in bestFriend:
            cnt += 1
          elif graph[nj][nk] == 0:
            emptyCnt += 1
            
        possible.append((cnt, emptyCnt, j, k))
  possible.sort(key=lambda x: (-x[0], -x[1], x[2], x[3]))
  j, k, x, y = possible[0]
  graph[x][y] = main
  
ans = 0
for i in range(a):
  for j in range(a):
    for k in range(len(friend)):
      if graph[i][j] == friend[k][0]:
        bestFriend = friend[k][1:5]
        cnt = 0
        for l in range(4):
          nx = i + dx[l]
          ny = j + dy[l]
          if nx < 0 or ny < 0 or nx >= a or ny >= a:
            continue
          if graph[nx][ny] in bestFriend:
            cnt += 1
        ans += happy[cnt]
print(ans)

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

문제 해결을 위한 과정

구현 유형에 해당하는 문제 이므로 문제에서 주어진 조건을 따라서 차분하게 작성하면 어렵지 않게 풀 수 있는 문제 입니다. 문제의 예시를 보고 한 단계씩 확인하면서 작성하여 크게 어렵지 않게 해결할 수 있었습니다.

소스코드

n, m = map(int, input().split())
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
moves = []
for _ in range(m):
  x, y = map(int, input().split())
  moves.append((x-1, y))
cloud = [(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)]

def move_cloud(d, s):
  length = len(cloud)
  for i in range(length):
    x, y = cloud[0]
    cloud.pop(0)
    nx = x + dx[d] * s
    ny = y + dy[d] * s
    nx = nx % n
    ny = ny % n
    cloud.append((nx, ny))

for i in range(len(moves)):
  d, s = moves[i]
  move_cloud(d, s)
  for j in range(len(cloud)):
    x, y = cloud[j]
    graph[x][y] += 1
  for j in range(len(cloud)):
    x, y = cloud[j]
    count = 0
    for k in range(1, 8, 2):
      nx = x + dx[k]
      ny = y + dy[k]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if graph[nx][ny] >= 1:
        count += 1
    graph[x][y] += count 
  tempCloud = []
  for a in range(n):
    for b in range(n):
      if graph[a][b] >= 2 and (a, b) not in cloud:
        tempCloud.append((a, b))
  cloud.clear()
  for j in range(len(tempCloud)):
    x, y = tempCloud[j]
    cloud.append((x, y))
    graph[x][y] -= 2

ans = 0
for i in range(n):
  for j in range(n):
    ans += graph[i][j]
print(ans)

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

문제 해결을 위한 과정

이 문제의 경우 백트레킹 및 dfs 방식으로 해결할 수 있었다. dfs함수를 짜는 건 어렵지 않았지만 이동하는 함수 moveGraph 함수는 작성하기 어려웠다. 다만 차근차근 조건을 따져가며 작성하니 생각보다는 어렵지 않았던 문제였다. https://chldkato.tistory.com/163 이 분의 포스팅을 참조하여 소스코드를 작성하였다. 구현 유형을 조금 더 많이 접하여 친숙해진다면 보다 쉽게 해결할 수 있을것으로 기대된다.

소스코드 - python

import copy

def move(dir): # n e s w
    if dir == 0:
        for j in range(n):
            idx = 0
            for i in range(1, n):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx += 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp  
                    elif graph[idx][j] != temp:
                        idx += 1
                        graph[idx][j] = temp
                        

    elif dir == 1:
        for i in range(n):
            idx = n-1
            for j in range(n-2, -1, -1):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx -= 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx -= 1
                        graph[i][idx] = temp
                        
    
    elif dir == 2: # s
        for j in range(n):
            idx = n-1
            for i in range(n-2, -1, -1):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx -= 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp
                    elif graph[idx][j] != temp:
                        idx -= 1
                        graph[idx][j] = temp
                        

    elif dir == 3: # w
        for i in range(n):
            idx = 0
            for j in range(1, n):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx += 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx += 1
                        graph[i][idx] = temp
                        

def dfs(count):
    global ans, graph
    if count == 5: # 5인 경우
        for i in range(n):
            ans = max(ans, max(graph[i]))
        return

    copyGraph = copy.deepcopy(graph)
    for i in range(4):
        move(i)
        dfs(count + 1)
        graph = copy.deepcopy(copyGraph)
        

n = int(input())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
ans = 0
dfs(0)
print(ans)

소스코드 - c++

#include <bits/stdc++.h>
#define MAX 21	
using namespace std;

int n;
int graph[MAX][MAX];
int ans;

void moveGraph(int dir) { // N, E, S, W
	if (dir == 0) {
		for (int j = 0; j < n; j++) {
			int idx = 0;
			for (int i = 1; i < n; i++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx += 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx += 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else if (dir == 1) {
		for (int i = 0; i < n; i++) {
			int idx = n-1;
			for (int j = n-2; j > -1; j--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx -= 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx -= 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}

	else if (dir == 2) {
		for (int j = 0; j < n; j++) {
			int idx = n-1;
			for (int i = n-2; i > -1; i--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx -= 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx -= 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else {
		for (int i = 0; i < n; i++) {
			int idx = 0;
			for (int j = 1; j < n; j++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx += 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx += 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}
}

void dfs(int count) {
	if (count == 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ans = max(ans, graph[i][j]);
			}
		}
		return;
	}

	int copyGraph[MAX][MAX] = { 0, };
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copyGraph[i][j] = graph[i][j];
		}
	}

	for (int k = 0; k < 4; k++) {
		moveGraph(k);
		dfs(count + 1);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				graph[i][j] = copyGraph[i][j];
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
		}
	}
	dfs(0);
	cout << ans;
	return 0;
}

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

문제 해결을 위한 과정

구현 유형에 해당하는 문제 이므로 문제에서 주어진 조건을 따라서 차분하게 작성하면 쉽게 해결할 수 있는 문제 입니다. bfs를 통해 이동할 수 있는 구역을 탐색한 후 먹을 수 있는 물고기들을 배열에 담아 정렬 후 가장 첫번째에 있는 물고기를 먹으면 되는 문제 입니다.

소스코드 - python

from collections import deque

def bfs(x, y, size, visited):
  q = deque()
  q.append((x, y))
  count = 0
  visited[x][y] = 1
  while q:
    for _ in range(len(q)):
      x, y = q.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
          continue
        if graph[nx][ny] <= size and visited[nx][ny] == 0:
          q.append((nx, ny))
          visited[nx][ny] = 1
          if 0 < graph[nx][ny] < size:
            eatable.append((count+1, nx, ny))
    count += 1

n = int(input())
graph = []
x = 0
y = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
size = 2 
eatable = []

for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    if graph[i][j] == 9:
      x, y = i, j
      graph[i][j] = 0

timeInfo = 0
eatCount = 0
while True:
  visited = [[0] * n for _ in range(n)]
  bfs(x, y, size, visited)
  if len(eatable) == 0:
    print(timeInfo)
    break
  eatable.sort()
  dist, xPos, yPos = eatable[0]
  eatable = []
  x, y = xPos, yPos
  graph[x][y] = 0
  timeInfo += dist
  eatCount += 1
  if eatCount == size:
    size += 1
    eatCount = 0

소스코드 - c++

#include <bits/stdc++.h>

using namespace std;

int graph[20][20];
int visited[20][20];
int n;
int sizeOfShark;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
vector<tuple<int, int, int>> eatable; // 거리, x좌표, y좌표

void bfs(int xPos, int yPos) {
	queue<pair<int, int>> q;
	q.push(make_pair(xPos, yPos));
	visited[xPos][yPos] = 1;
	int num = 0;
	int distance = 0;

	while (!q.empty()) {
		num = q.size();
		for (int i = 0; i < num; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
					continue;
				}
				if (graph[nx][ny] <= sizeOfShark && visited[nx][ny] == 0) {
					q.push(make_pair(nx, ny));
					visited[nx][ny] = 1;
					if (0 < graph[nx][ny] && graph[nx][ny] < sizeOfShark) {
						eatable.push_back(make_tuple(distance + 1, nx, ny));
					}
				}
			}
		}
		distance += 1;
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int x = 0, y = 0; // 상어 좌표
	sizeOfShark = 2; // 초기 상어 크기

	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j]; // 그래프 입력 받기
			if (graph[i][j] == 9) { // 상어 위치인 경우
				x = i;
				y = j;
				graph[i][j] = 0;
			}
		}
	}

	int timeInfo = 0;
	int eatCount = 0;

	while (true) {
		fill(&visited[0][0], &visited[19][20], 0);
		bfs(x, y);
		if (eatable.size() == 0) {
			cout << timeInfo;
			break;
		}
		sort(eatable.begin(), eatable.end());
		int dist = get<0>(eatable[0]);
		int xPos = get<1>(eatable[0]);
		int yPos = get<2>(eatable[0]);
		eatable.clear();
		x = xPos;
		y = yPos;
		graph[x][y] = 0;
		timeInfo += dist;
		eatCount += 1;
		if (eatCount == sizeOfShark) {
			sizeOfShark += 1;
			eatCount = 0;
		}
	}
	return 0;
}

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

문제 해결을 위한 과정

이 문제의 경우 알고리즘의 분류상 구현 문제로 문제에서 주어진 대로만 차분하게 구현하면 쉽게 해결할 수 있는 문제였습니다. 다만 실버 5 티어라는 난이도에 비해 정답률이 29%로 낮은 편인데 그 이유는 메모리 제한 때문이라 생각됩니다. 저 역시 pypy3로 풀었을 때 메모리 초과 판정을 받았고 pypy는 시간 복잡도가 좋은 대신 공간 복잡도 측면에서 불리하다는 사실을 알게 되어 python3으로 해결한 결과 정답 판정을 받을 수 있었습니다. 문제의 조건을 그대로 구현하면 되는 문제이기 때문에 해결방안은 따로 제시하지 않습니다.

소스코드

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

문제 해결을 위한  과정

이 문제의 경우 골드 4 티어로 비교적 높은 난이도를 가지고 있지만 사실 구현으로 분류되는 문제의 특성상 차분하게 문제에서 제시한 조건을 따라가면 쉽게 해결할 수 있는 문제였습니다. 다만 주사위라는 공간지각 능력이 필요한 문제라서 조금 생각을 해야 합니다. 이 문제를 푸는 데 있어서 가장 중요한 것은 전개도입니다. 전개도 대로 주사위를 만들면 아래의 그림과 같습니다. 

이를 동쪽, 서쪽, 남쪽, 북쪽으로 돌리더라도 주사위의 특성상 마주보는 면의 합은 7입니다. 위 주사위 그림의 면에 배정된 숫자는 문제에서 주어진 조건 "주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여 있는 곳의 좌표는 (x, y)이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다." 를 반영한 것입니다. 즉 위치를 저렇게 잡은 후 모든 주사위의 면을 0으로 초기화합니다. 그 후 문제에서 테스트 케이스로 주어진 지도에 0행 0열에 주사위를 배치합니다. 첫 번째 예시에서 맵은 다음과 같습니다.

과정 및 주사위 그림은 다음과 같습니다.

1. 시작지점에 위치(0행 0열)

2. 명령이 4 이므로 남쪽으로 회전 1행 0열이 3 이므로 주사위의 밑면은 3, 윗면은 0이 됨 따라서 0 출력

3. 명령이 4 이므로 남쪽으로 회전 2행 0열이 5 이므로 주사위의 밑면은 5, 뒷면은 3, 윗면은 0이 됨 따라서 0 출력

4. 명령이 4 이므로 남쪽으로 회전 3행 0열이 7 이므로 주사위의 밑면은 7 뒷면은 5 윗면은 3이 됨 따라서 3 출력

5. 명령이 1 이므로 동쪽으로 회전 3행 1열이 8 이므로 주사위의 밑면은 8 왼쪽면은 7 오른쪽면은 3 뒷면은 5 윗면은 0 따라서 0 출력

이러한 과정을 반복한다.

문제 해결을 위한 팁

처음의 주사위의 전개도를 2차원 리스트의 형태로 구현한 후 문제를 해결하려 하였으나 예상보다 복잡해지는 바람에 다른 방법을 찾던 중 단순하게 일차원 리스트로 해결할 수 있음을 알게 되었고 해결방법은 다음과 같다. 먼저 리스트를 다음과 같이 설정한다.

dice = [0, 0, 0, 0, 0, 0]

그 후 이 그림을 보면서 항상 리스트의 0번째가 윗면, 1번째가 앞면, 2번째가 오른쪽면 이런 식으로 5번째가 아래쪽면이라는 것을 고정한 뒤 swap을 해준다. 즉 남쪽으로 한번 회전을 해주면 위의 그림에서 왼쪽 오른쪽면은 그대로 있고 나머지 4면이 회전을 하는 형태이다. 따라서 이를 이렇게 표현할 수 있다.

if 남쪽으로 회전할 시:

    dice[5], dice[1], dice[0], dice[4] = dice[1], dice[0], dice[4], dice[5] 

이를 전체의 경우에 적용하면 쉽게 해결할 수 있다. 소스코드는 아래와 같다.

소스코드