배극곰의 IT식량창고

문제링크

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

문제설명

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Escaped in 11 minute(s).
Trapped!

문제풀이

3차원을 잘 이해해야 하고,

입력값 받는게 좀 어려웠던것 같다.  (삽질을 좀 많이했다...)

인덱스에 변수로 접근시 맞게 했는지 잘 확인하고 (여기서 실수를 했는데 찾지 못해서 시간이 오래 소요됨..)

그거말고는 BFS로 풀면 똑같이 풀린다.

핵심

1. 3차원배열

2. 입력값받기

코드

from collections import deque
    
def BFS(x, y, z):
    queue = deque([(x, y, z)])
    visited[z][x][y] = 0
    while queue:
        curX, curY, curZ = queue.popleft()
        if graph[curZ][curX][curY] == 'E':
            print('Escaped in {0} minute(s).'.format(visited[curZ][curX][curY]))
            return
        for dx, dy, dz in d:
            nx = curX + dx
            ny = curY + dy
            nz = curZ + dz
            if 0 <= nx < R and 0 <= ny < C and 0 <= nz < L and visited[nz][nx][ny] == -1:
                if graph[nz][nx][ny] == '.' or graph[nz][nx][ny] == 'E':
                    queue.append((nx, ny, nz))
                    visited[nz][nx][ny] = visited[curZ][curX][curY] + 1
    
    print('Trapped!')

while True:
    L, R, C = map(int, input().split())
    if L == 0 and R == 0 and C == 0:
        break
    graph = []
    visited = [[[-1 for k in range(C)] for j in range(R)] for i in range(L)]
    d = [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)]
    for _ in range(L):
        layer = [list(input()) for _ in range(R)]
        graph.append(layer)
        input()

    for k in range(L):
        for i in range(R):
            for j in range(C):
                if graph[k][i][j] == 'S':
                    BFS(i, j, k)

문제링크

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

문제설명

2 20 50
50 30
20 40

1

문제풀이

시뮬레이션 문제는 단순히 문제를 이해하기에도 시간이 적지않게 걸리는 것 같다.

더 많은 연습이 필요해보인다...

연합이 될 수 있는 조건이 있고,

하루동안 연합국들끼리 인구를 조건에 맞게 이동하는 로직을 구현해야하는 문제다.

크게 나눠서,

1. 연합을 정의하는 로직을 BFS함수에 구현하였다.

2. 하루동안 인구를 이동시키는 로직이 그 아래에 있는 메인 코드이다.

여기서 개인적으로 생각하는 핵심은,

하루동안 연합이 형성 될때, 이때 연합국이 여러개가 될 수 있다는 점이다.

BFS문제에서 많이 연습했던 구역나누는 로직을 생각해보면 이해가 빠르다.

cf. 적록색약 문제

코드

from collections import deque

N, L, R = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
day = 0

# 여기서 BFS함수는 하루동안 연합인 국가를 정의하는 역할.
def BFS(x, y):
    queue = deque([(x, y)])
    union.append((x, y))
    visited[x][y] = 1

    while queue:
        curX, curY = queue.popleft()

        for dx, dy in d:
            nx = curX + dx
            ny = curY + dy

            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:  
                gap = abs(A[nx][ny] - A[curX][curY])
                # 조건 통과하면 연합 형성. 그러고 방문.
                if L <= gap <= R:
                    visited[nx][ny] = 1
                    queue.append((nx, ny))
                    union.append((nx, ny))
    
    if len(union) > 1:
        return True
    else:
        return False

# 하루 동안 인구 이동 로직.
while True:
    visited = [[0 for _ in range(N)] for _ in range(N)]
    exist = 0

    # 연합국이 여러개 일 수 있으므로 for문 돌려서 BFS시행 (방문한 지역 제외)
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                union = []
                # BFS 시행 후 연합국가 있으면
                if BFS(i, j):
                    exist = 1
                    people = sum(A[x][y] for x, y in union)
                    for x, y in union:
                        A[x][y] = people // len(union) 
    
    if not exist:
        print(day)
        break      
    day += 1

개인적으로 이해에 도움이 많이 됐던 블로그

https://tmdrl5779.tistory.com/142

문제링크

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

문제설명

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

2

문제풀이

처음시도한 방법 (이것도 정답코드)

from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, -1, -1, 1, 1, 1, 0, 0]
dy = [0, 1, -1, 0, -1, 1, -1, 1]

def BFS(x, y):
    queue = deque([(x, y, 0)])
    visited[x][y] = 1

    while queue:
        curX, curY, dist = queue.popleft()

        if graph[curX][curY] == 1:
            return dist

        for i in range(8):
            nx = curX + dx[i]
            ny = curY + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                queue.append((nx, ny, dist+1))
                visited[nx][ny] = 1

tmpSet = set()

for i in range(N):
    for j in range(M):
        visited = [[0 for _ in range(M)] for _ in range(N)]
        if graph[i][j] == 0:
            tmpSet.add(BFS(i, j))

print(max(list(tmpSet)))

# 1. 각 좌표마다 1을 만날때까지 BFS 시행하여 최단거리 구해서 임시배열에 저장
# 2. 임시 배열에서 최댓값 구하기

하지만 난 모든 빈 좌표에서 BFS를 시행하여 상어까지의 최단거리를 구했다.

좀 더 최적화가 필요해보여서 생각해낸 방법이,

상어가 있는 좌표들에서 시작을 해보자 

=> 연산속도가 훨씬 빨라진다. (4000ms -> 72ms)

★핵심

1. 상어가 있는 좌표들을 큐에 전부 삽입.

2. 그러고 나서 큐에 있는거 기반으로 BFS 시행

3. BFS 직후 저장된 안전거리들의 최댓값 산출

코드

from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, 1), (0, -1), 
     (-1, -1), (-1, 1), (1, -1), (1, 1)]
visited = [[-1 for _ in range(M)] for _ in range(N)]
queue = deque()

def BFS():
    while queue:
        curX, curY = queue.popleft()

        for dx, dy in d:
            nx = curX + dx
            ny = curY + dy
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 0:
                if visited[nx][ny] == -1:
                    visited[nx][ny] = visited[curX][curY] + 1
                    queue.append((nx, ny))

# 상어좌표 전부 큐에 삽입
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            queue.append((i, j))
            visited[i][j] = 0

# 큐에 좌표 삽입했으니, BFS 시행
BFS()

# BFS 종료후 visited에 삽입된 안전거리의 최댓값 구하기
maxValue = 0
for row in visited:
    maxValue = max(maxValue, max(row))

print(maxValue)

# 상어가 있는 1인 좌표에서 부터 BFS시행 (최단거리를 잼)

문제링크

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

문제설명

4 3
1 1 2 0
2 0 1 0
3 0 1 0
4 0 0 1

2

문제풀이

구현문제에 취약한 것 같아 연습하고 있는데,

역시나 티어에 비해서 어려운것 같다.. 나만 그런건지 모르겠다.

핵심

- ★정렬

  우선순위를 정하여 금메달 인덱스 기준으로 정렬, 은메달, 동메달 순서로 정렬하는 코드

- 여러가지 슬라이싱 문법이나 해당하는 값의 인덱스 뽑기 등 문법 익히기

코드

N, K = map(int, input().split())
medals = [list(map(int, input().split())) for _ in range(N)]
targetIdx = 0

# ★정렬 (금메달우선, 그다음 은메달우선, 그다음 동메달우선) 각각 내림차순으로
sortArr = sorted(medals, key=lambda x: (-x[1], -x[2], -x[3]))

for idx, item in enumerate(sortArr):
    if item[0] == K:
        targetIdx = idx
        
# K국가의 인덱스를 뽑아서 sortArr조회
for i in range(len(sortArr)):
    if sortArr[i][1:] == sortArr[targetIdx][1:]:
        print(i+1)
        break

문제링크

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

문제설명

5 17

4
5 10 9 18 17

5 17

4
5 4 8 16 17

문제풀이

처음 시도한 방법 (틀린 코드)

from collections import deque

N, K = map(int, input().split())
M = 100000
dist = [[-1, []] for _ in range(M+1)]

def BFS(start):
    queue = deque([start])
    dist[start][0] = 0
    dist[start][1].append(start)

    while queue:
        cur = queue.popleft()

        if cur == K:
            print(dist[K][0])
            print(*dist[K][1])

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                if dist[next][0] == -1:                
                    queue.append(next)
                    dist[next][0] = dist[cur][0] + 1
                    for i in dist[cur][1]:
                        dist[next][1].append(i)
                    dist[next][1].append(next)

BFS(N)

이렇게 시도했었는데 당연히 각 노드까지의 전체경로를 매번 저장하려고 하니 메모리 초과가 나는건 당연한 일이었다.

해결방법

- 각 노드까지 경로 중 직전 노드정보만 저장하자!

 => 그래서 목표노드에 도달하면 역 추적을 통해 경로를 알 수 있다.

코드

from collections import deque

N, K = map(int, input().split())
M = 100000
dist = [[-1, -1] for i in range(M+1)] # 첫번째 인덱스의 값으로 최소시간 저장, 두번째 인덱스 값으로는 직전노드 정보 저장
path = []

def BFS(start):
    queue = deque([start])
    dist[start][0] = 0

    while queue:
        cur = queue.popleft()

        # 목표 노드에 도달하면 dist[cur][1](직전 노드정보)에 있는 원소들을 조회하며 하나씩 역으로 조회하기
        if cur == K:
            print(dist[K][0])
            while cur != -1:
                path.append(cur)
                cur = dist[cur][1]
            for i in range(len(path)-1, -1, -1):
                print(path[i], end=' ')

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                # 방문안한 노드라면 
                if dist[next][0] == -1:                
                    queue.append(next)
                    dist[next][0] = dist[cur][0] + 1
                    dist[next][1] = cur	# 직전 노드 정보 저장

BFS(N)


# 최단시간 출력하고
# 이동 경로까지 출력

문제링크

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

문제설명

5 17

4
2

문제풀이

처음 시도한 코드 (틀린 코드)

from collections import deque

N, K = map(int, input().split())
M = 100000
dist = [(0, 0) for _ in range(M+1)]

def BFS(start):
    queue = deque([start])

    while queue:
        cur = queue.popleft()

        if cur == K:
            print(dist[cur][0])
            print(dist[cur][1])
            return

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                # 이전에 방문한 노드가 아니라면
                if not dist[next][0]:
                    queue.append(next)
                    dist[next] = (dist[cur][0] + 1, 1)
                # 이미 방문한적이 있다면, 더 최소시간으로 갱신
                else:
                    # 방문할 노드의 최소시간과 이미 저장된 최소시간이 같다면 방법수 1증가
                    if dist[next][0] == dist[cur][0] + 1:
                        dist[next] = (dist[next][0], dist[next][1] + dist[cur][1])
                    minValue = min(dist[next][0], dist[cur][0] + 1)
                    dist[next] = (minValue, dist[next][1])

BFS(N)

- 튜플로 처리했었는데 다시보니 코드자체도 굉장히 보기 불편하다...

- 그리고 dist[next] = (dist[cur][0] +1 , 1) 부분이 문제였다

=> 다시 생각하면 당연한 일인데... 1이 아니라 이전값인 dist[cur][1]를 그대로 가져가야한다.

- 최소시간으로 도달하는 방법수를 전부 세야하므로 K에 도달했다고 해서 바로 출력해버리면 안되고 BFS시행이 끝나고 나서 값에 접근해야함

핵심

- dist : 열이 2개인 이차원배열로 만든다.

  첫번째 인덱스 원소 : 최소시간을 의미

  두번째 인덱스 원소:  최소시간으로 거리에 도달하는 방법수를 의미

 cf. 처음엔 튜플로 묶었으나 튜플은 불변한 특성이 있기 때문에 값을 변경하기 위해서는 재할당으로 처리해야하는 번거로움이 있다 => 리스트로 묶은 이유.

- 최소시간으로 도달하는 방법수를 다 세야하므로 BFS()시행이 끝난후에 값을 조회하기.

- 숨바꼭질2는 걷기, 순간이동 모두 비용이 1초이므로, 이미 방문한 노드에 대해 최단시간 값 갱신을 할 필요가 없다.

   => BFS로 항상 최단시간 찾기 가능

  cf. 숨바꼭질3은 순간이동 비용이 0초이므로, BFS내에서도 최단시간 값 갱신이 필요하다.

코드

from collections import deque

N, K = map(int, input().split())
M = 100000
dist = [[-1, 0] for _ in range(M+1)] #첫번째 인덱스는 최소시간을 의미, 두번째는 최소시간으로 도달하는 방법수를 의미

def BFS(start):
    queue = deque([start])
    dist[start] = [0, 1]

    while queue:
        cur = queue.popleft()

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                # 이전에 방문한 노드가 아니라면
                if dist[next][0] == -1:
                    queue.append(next)
                    dist[next] = [dist[cur][0] + 1, dist[cur][1]]
                # 이미 방문한적이 있다면, 더 최소시간으로 갱신
                else:
                    # 방문할 노드의 최소시간과 이미 저장된 최소시간이 같다면 방법수 1증가
                    if dist[next][0] == dist[cur][0] + 1:
                        dist[next][1] += dist[cur][1]
                    dist[next][0] = min(dist[next][0], dist[cur][0] + 1)
                    

BFS(N)
print(dist[K][0])
print(dist[K][1])

문제링크

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

문제설명

5 17

2

문제풀이

숨바꼭질 문제처럼 BFS 이용하면 된다.

핵심

- dist 리스트는 최단시간정보를 저장. (각 인덱스는 거리를 의미한다)

- 순간이동의 비용이 0 이다.

- 즉, 방문한 노드일 경우 최단시간정보를 비교하여 최솟값 갱신할 필요가 있다.

  (이전 숨바꼭질1 , 숨바꼭질2와 다른점)

코드

from collections import deque
N, K = map(int, input().split())
M = 100000
dist = [-1] * (M+1) # 해당 인덱스는 거리를 의미, 원소값으로 최단시간정보 저장.

def BFS(start):
    queue = deque([start])
    dist[start] = 0

    while queue:
        cur = queue.popleft()

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                # 방문체크, 방문 안한노드라면
                if dist[next] == -1:
                    queue.append(next)
                    # 순간이동한 경우
                    if next == cur*2:
                        dist[next] = dist[cur]
                    else:
                        dist[next] = dist[cur] + 1
                # 방문한 노드라면
                else:
                    if next == cur*2:
                        dist[next] = min(dist[cur], dist[next])
                    else:
                        dist[next] = min(dist[cur]+1, dist[next])

BFS(N)
print(dist[K])
# 동생을 찾을 수 있는 가장 빠른 시간 찾는 문제

문제링크

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

문제설명

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

5

문제풀이

생각보다 문제를 이해하는데 시간이 오래걸렸던 문제다;

주어진 이차원 배열에서 최댓값(높이)을 찾아서,

0부터 최댓값까지 반복문을 돌려 조건에 맞는 좌표에서 BFS를 시행하는 것이 핵심이다.

(아무지역도 잠기지 않을 수 있다 했으므로 범위가 0부터 지정되는것이 맞다.)

코드

from collections import deque

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
maxNum = 0
maxValue = 0

def BFS(x, y, k):
    queue = deque([(x, y)])
    visited[x][y] = 1
    
    while queue:
        curX, curY = queue.popleft()

        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]
            
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] > k and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = 1

# 입력받은 2차원 배열에서 최댓값 찾는다
for row in graph:
    for item in row:
        maxNum = max(item, maxNum)

# 조건에 맞는 좌표를 시작점으로 BFS 강행
for k in range(maxNum + 1):
    cnt = 0
    visited = [[0 for _ in range(N)] for _ in range(N)]
    
    for i in range(N):
        for j in range(N):
            if graph[i][j] > k and not visited[i][j]:
                BFS(i, j, k)
                cnt += 1
    maxValue = max(cnt, maxValue)
    
print(maxValue)

문제링크

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

문제설명

문제풀이

어렵지 않게 구현 가능한 문제이다.

나는 파이썬의 딕셔너리를 이용하여 풀었지만,

set을 이용하면 더 편할 것 같다.

코드

import sys
input = sys.stdin.readline

N = int(input())
dict = {}

def add(x):
    if x not in dict:
        dict[x] = 1

def remove(x):
    if x in dict:
        del dict[x]

def check(x):
    if x in dict:
        print(1)
    else:
        print(0)

def toggle(x):
    if x in dict:
        del dict[x]
    else:
        dict[x] = 1

def all():
    dict.clear()
    for i in range(20):
        dict[i+1] = 1

def empty():
    dict.clear()

for i in range(N):
    num = 0
    arr = input().split()
    
    if len(arr) == 1:
        command = arr[0]
    else:
        command, num = arr[0], arr[1]

    if not num:
        if command == 'all':
            all()
        elif command == 'empty':
            empty()
    else:
        N = int(num)
        if command == 'add':
            add(N)
        elif command == 'check':
            check(N)
        elif command == 'remove':
            remove(N)
        elif command == 'toggle':
            toggle(N)

또 다른 정답코드

import sys
input = sys.stdin.readline

S = set()
N = int(input())

for _ in range(N):
    arr = input().split()

    if len(arr) == 1:
        command = arr[0]
        if command == 'all':
            S = set([i for i in range(1, 21)])
        else:
            S = set()
    else:
        command, num = arr[0], arr[1]
        x = int(num)

        if command == 'add':
            S.add(x)
        elif command == 'remove':
            S.discard(x)
        elif command == 'check':
            print(1 if x in S else 0)
        elif command == 'toggle':
            if x in S:
                S.discard(x)
            else:
                S.add(x)

문제링크

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

문제설명

4 7
6 13
4 8
3 6
5 12

14

문제풀이

냅색 알고리즘 핵심

특정 물건을 담지 않았을때 오히려 최선의 선택이 될 수 있음을 고려.

D[i][j] : 배낭 무게한도가 j일때, i번째 물건까지 고려했을때 최대가치

한도 무게가 더 작으면 현재인덱스에 있는 물건을 고려할 필요 없으므로,

이전 인덱스의 물건까지 고려한 상태에서의 최대가치값으로 저장 => D[i][j] = D[i-1][j]

하지마 한도무게가 현재물건 무게보다 크다면,

[1] 이전 물건까지 고려한 dp리스트 값 D[i-1][j-W[i]] 에 현재물건 가치 V[i] 를 더한 D[i-1][j-W[i] +V[i]

[2] D[i-1][j] 현재 물건안하고 이전에 저장해놓은 최댓값이 더 클수도 있으므로

이 둘의 max값을 구하여 저장

코드

N, K = map(int, input().split())
D = [[0 for _ in range(K+1)] for _ in range(N)]
W = [0] * N
V = [0] * N

for i in range(N):
    w, v = map(int, input().split())
    W[i] = w
    V[i] = v

for j in range(W[0], K+1):
    D[0][j] = V[0]

# D[i][j] : 배낭한도무게가 j일때, i번째 물건까지 중 담을 수 있는 최대가치
for i in range(1, N):
    for j in range(1, K+1):
        # 배낭한도무게가 현재차례의 물건의 무게보다 클때
        # 후보 2개중 더 큰값으로 저장
        if j >= W[i]:
            D[i][j] = max(D[i-1][j-W[i]] + V[i], D[i-1][j])
        # 한도무게가 더 작을때
        # 더 넣지 못하므로 이전물건까지 고려한 상태에서의 최대가치로 저장
        else:
            D[i][j] = D[i-1][j]

print(D[N-1][K])