4/1 Coding Test

✅ 문제 풀이 - BOJ (Greedy)

🎈 1758 알바생 강호

손님들이 가게에 입장할 때 주는 팁 금액은 원래 주려고 한 돈 - (받은 등수-1)이다.
첫 줄에 손님 수 n, 둘째 줄부터 n줄 동안 각 사람이 주려는 팁이 주어질 때 손님 순서를 적절히 바꾸어 알바생이 받는 최대 값을 구하는 문제

import sys
input = sys.stdin.readline

n = int(input())
cash = []
for _ in range(n):
    pay = int(input())
    cash.append(pay)
answer = 0
cash.sort(reverse = True)
for i in range(len(cash)):
    if cash[i] > i:
        answer += (cash[i]-i)
print(answer)

< 풀이 과정 >
돈을 얻는 방식은 원래 주려는 금액 - (등수 - 1)이므로, 결국 원래 주려는 금액이 애초에 높은 손님이 앞 순서에 세워야 한다.

따라서 입력받는 pay를 cash 리스트에 넣은 후 내림차순 정렬을 한다.
for문으로 돈을 받는데, 금액이 양수인 조건만 받아준다.

🎈 19941 햄버거 분배

첫 줄에 식탁 길이 n, 햄버거를 선택할 수 있는 길이 k가 주어지고 둘째줄에는 사람과 햄버거의 위치가 각각 P,H 로 주어질 때 햄버거를 먹을 수 있는 최대 사람 수를 구하는 문제

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
table = list(input().rstrip())
person = 0
for i in range(n):
    if table[i] == 'P':
        for j in range(i-k, i+k+1):
            if 0<=j<n and table[j] == 'H':
                person += 1
                table[j] = 'False'
                break
print(person)

< 풀이 과정 >
주어진 n의 범위가 20,000이하임을 발견하고 2중 for문을 사용
for문으로 0~n까지의 i를 저장하고 우선 사람 위치를 조건문으로 걸어준다.
그 이후 for문으로 i-k, i+k+1 범위 내 햄버거 위치가 존재한다면 해당 햄버거 위치는 없애주고 먹은 것으로 처리한다.

✅ 문제 풀이 - BOJ (그래프 탐색)

🎈 10026 적록색약

NXN 크기의 그리드에 각 칸에 R, G, B 중 하나를 칠한 그림이 있고 그림은 같은 색으로 구성된 몇 개의 구역으로 나뉘게 된다. 여기서 같은 구역이란 상하좌우에 같은 색상이 인접한 경우를 의미한다. 최종적으로 주어진 그리드에서 적록색약이 아닌 사람이 보았을 때 구역의 개수와 적록색약인 사람이 보았을 때 구역의 개수를 공백으로 구분해 출력하는 문제

import sys
input = sys.stdin.readline
import copy
sys.setrecursionlimit(10**6)

n = int(input())
# 적록색약 아닌 사람이 보는 그래프 & 구역 수
graph = [list(input().rstrip()) for _ in range(n)]
graph_answer = 0
# 상하좌우 4방향
dx = [-1, 1, 0 ,0]
dy = [0, 0, -1, 1]
# 적록색약인 사람이 보는 그래프 생성 위해 깊은 복사 진행하여 그래프 및 구역 수 변수 저장
disease = copy.deepcopy(graph)
for i in range(n):
    for j in range(n):
        if disease[i][j] == 'G':
            disease[i][j] = 'R'
disease_answer = 0
# 방문한 곳 여부 확인 위해 생성
visited = [[0]*n for _ in range(n)]
# dfs 함수에 현좌표 , 그래프 입력
def dfs(x, y, matrix):
	# 현위치 방문 처리 및 현위치의 color 저장
    visited[x][y] = 1
    now_color = matrix[x][y]
    # 상하좌우 4방향 탐색 진행
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 다음 좌표가 주어진 범위이고 방문하지 않았으며 같은 색깔인 경우에만 재귀진행
        if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and matrix[nx][ny] == now_color:
            dfs(nx, ny, matrix)
# 적록색약이 아닌 사람이 보는 그래프의 구역 수 구하기
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j, graph)
            graph_answer += 1
# visited 재생성 (적록색약인 사람들이 보는 그래프의 dfs탐색을 위해)
visited = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j, disease)
            disease_answer += 1
print(graph_answer, disease_answer)

< 풀이 과정 >
주어진 그리드 즉 그래프를 통해 dfs탐색을 활용하여 같은 색깔인지 여부를 판단하며 구역수를 구하도록 구현하였다. deepcopy를 활용하여 적록색약이 아닌 사람이 보는 그래프와 적록색약인 사람이 보는 그래프를 만들어주었다. (vistied도 어차피 만들어야해서 deepcopy활용함)
이후 구현은 dfs함수를 제외하면 반복 느낌으로 간단하였다.

• dfs함수는 결국, 현 위치의 색깔을 저장하고 방문 처리하여 다음 위치 역시 같은색인지 여부를 판단해가며 재귀한다.
• 적록색약인 사람 vs 적록색약이 아닌 사람들이 보는 그래프를 비교하기 위해 visited를 2회 만들었고 최종적으로 각 그래프 내 나뉘어진 구역 수를 출력하였다.

🎈 2206 벽 부수고 이동하기

nxm 크기의 맵이 있다. 맵에서 0은 이동할 수 있는 곳이고 1은 벽을 나타낸다. (1,1)에서 (n, m)으로 최단 경로를 활용해 이동하고자 한다.
최단 경로는 시작 칸, 끝 칸을 포함하여 칸 수를 세야 하며, 이동 중 벽을 최대 1개까지 부셔서 이동할 수 있다. 이동 방향은 상하좌우로 4방향이며 최단 거리가 불가능한 경우 -1을 출력한다.
시작점은 (1,1)로 고정되고 도착점 역시 (m, n)으로 고정된다.

import sys
input = sys.stdin.readline
from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
# visited[x][y][z]에서 z=0 : 통과 가능 , z=1 : 통과 X
visited = [[[0]*2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(a, b, c):
    queue = deque()
    queue.append((a, b, c))
    while queue:
        x, y, z = queue.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y][z]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m:
                # 다음 위치 벽이고, 통과 가능한 경우
                if graph[nx][ny] == 1 and z == 0:
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    queue.append((nx, ny, 1))
                # 다음 위치가 벽이 아닌 이동할 수 있는 칸의 경우
                elif graph[nx][ny] == 0 and not visited[nx][ny][z]:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    queue.append((nx, ny, z))
    return -1
print(bfs(0, 0, 0))

< 풀이 과정 >
세로(n), 가로(m), 그래프를 입력받고 벽 통과 여부를 확인하기 위해 visited를 3차원 리스트로 구현하였다. visited[x][y][z]에서 z가 0 or 1로 구분하여 각각 벽 통과가능, 불가능으로 나누었다.

이후 bfs로 deque를 만들어준 후 queue가 빌때까지 다음을 반복한다.
1. 현재 큐에 들어간 좌표 뽑아낸 후, 도착지이면 visited 도착지 리턴
2. 상하좌우 4방향 탐색 진행해 주어진 범위 내 만족하는 다음 좌표만 탐색
3. 다음 위치가 벽이고 통과 가능한 경우 다음좌표를 visited + 1, queue에 삽입. (이때 큐에 삽입되는 z는 1이다 벽을 통과했으므로)
4. 다음 위치가 일반적으로 이동할 수 있는 경우, nx,ny,z 좌표에 + 1, 큐에 삽입
5. 불가능한 경우 -1 리턴

최종적으로 bfs(0, 0, 0) 함수 결과를 print한다.