h32j00

문제

www.acmicpc.net/problem/1261

처음 작성한 코드

import sys
import heapq

M, N = map(int, sys.stdin.readline().split())
arr = []
queue = []
result = [sys.maxsize] * (M*N)
direction = [[-1,0], [0,1], [1,0], [0,-1]] #위, 오, 아래, 왼

result[0] = 0
heapq.heappush(queue, [0,0]) # 좌푯값[x,y]

for i in range(N):
    tmp = []
    line = map(int, sys.stdin.readline().rstrip())
    for j in line:
        tmp.append(j)
    arr.append(tmp)

while queue:
    x, y = heapq.heappop(queue)
    for i in direction:
        if 0 <= x+i[0] < N and  0 <= y+i[1] < M:
            new_x = x+i[0]
            new_y = y+i[1]
            if result[new_x * M + new_y] > result[x * M + y] + arr[new_x][new_y]:
                result[new_x * M + new_y] = result[x * M + y] + arr[new_x][new_y]
                heapq.heappush(queue, [new_x, new_y])

print(result[-1])

1. queue에는 인접한(위, 오, 아래, 왼) 좌표값들이 들어간다. 물론 최단 거리가 변경될 때에만 들어간다.
2. result에는 그 좌표까지의 최단 거리가 들어간다. 2차원 배열을 어떻게 선언하는지 잘 몰라서 1차원 배열로 했고 (0,0)은 [0]으로 접근, (0,1)은 [1]로 접근, (1,0) 은 [1*M+0] 이런식으로 접근했다.
3. 벽이 1이고 방이 0이라고 했으니까 벽을 부시고 방을 들어가면 벽 부신 횟수가 +1 이 되니까 그냥 좌표를 더해주면 된다. 그럼 빈방이면 +0, 벽이면 +1이 되기 때문이다.

깨달은 점

• 가중치 있는 그래프에서 최단 거리를 구하라고 할 때 다익스트라 알고리즘을 사용하면 될 것 같다. 

문제

www.acmicpc.net/problem/1916

처음 작성한 코드

import sys
from collections import deque

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
result = [sys.maxsize] * (N+1)
arr = {i+1:[] for i in range(N)}

for _ in range(M):
    u, v, w = map(int, sys.stdin.readline().split())
    arr[u].append([v,w])

s , e = map(int, sys.stdin.readline().split())

queue = deque()
result[s] = 0
queue.append(s)

while queue:
    u = queue.popleft()
    for v, w in arr[u]:
        if result[v] > result[u] + w:
            result[v] = result[u] + w
            queue.append(v)

print(result[e])

깨달은 점

• 단순한 다익스트라를 이용한 문제였다. 한 점에서 다른 점까지 최소거리를 구할 때 다익스트라를 쓰면 되는 것 같다. 손에 익으니까 재밌다 ㅋ ㅋ

문제

www.acmicpc.net/problem/1753

처음 작성한 코드

import sys
import heapq

V, E = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())
INF = sys.maxsize
graph = [INF] * (V+1)
queue = []
arr = {i+1:[] for i in range(V)}

for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    arr[u].append([v, w])

heapq.heappush(queue, [0, start])
graph[start] = 0

while queue:
    w, now = heapq.heappop(queue)
    for i in arr[now]:
        if graph[i[0]] > w+i[1]:
            graph[i[0]] = w+i[1]
            heapq.heappush(queue, [graph[i[0]], i[0]])

for i in range(1, V+1):
    print(graph[i] if graph[i]!=INF else 'INF')

깨달은 점

• 시간초과 5번 났는데 이유를 찾았다. 가중치가 변경될때만 queue에 넣어야하는데 안변경되도 queue에 넣어가지고 똑같은 점을 엄청 많이 방문하고 있었다....... 
• sys.maxsize를 알게됐다.
• heapq는 heap구조를 유지하며 push, pop 해주는 내장모듈인데 신기하다..

문제

www.acmicpc.net/problem/1446

처음 작성한 코드

import sys

N, D = map(int, sys.stdin.readline().split())
arr = []
for _ in range(N):
    s, e, leng = map(int, sys.stdin.readline().split())
    if e <= D:
        arr.append([s,e,leng])

distance = [i for i in range(D+1)]

for i in range(D+1):
    if i:
        distance[i] = min(distance[i], distance[i-1]+1)
    for j in arr:
        if j[0] == i:
            distance[j[1]] = min(distance[j[0]]+j[2], distance[j[1]])
    print(distance)

print(distance[-1])

1. 입력받을 때 고속도로의 길이(D)보다 지름길 끝 지점(e)이 크면 arr에 추가하지 않았다. -> 빠꾸할 수 없다고 문제에 나와있기때문에 그 지름길을 타봤자 소용이 없음.
2. 고속도로의 길이(D)만큼의 배열을 만들고 그 배열의 값을 갱신시켜주면서 최소 길이를 찾았다. -> 100킬로미터까지의 거리는 distance[100]에 접근하면 구할 수 있도록 만든것.. 마지막 출력값은 고속도로의 마지막까지의 거리를 나타낸다.

깨달은 점

• 너무너무너무 어렵다..  . . . . 언젠간 잘해지겠지..
• 다익스트라는 출발지점에서 도착지까지 최소 거리를 구할 때 사용된다고 한다.. 기억이 하나도 안난다 푸 헹헹..

문제

www.acmicpc.net/problem/4963

처음 작성한 코드

import sys
from collections import deque

def BFS(i, j):
    x = [1, 1, 1, 0, 0, -1, -1, -1]
    y = [1, 0, -1, 1, -1, 1, 0, -1]

    queue = deque()
    queue.append((i,j))

    while queue:
        now = queue.popleft()
        for i in range(8):
            next_x = now[0] + x[i]
            next_y = now[1] + y[i]
            
            if (0 <= next_x < h) and (0 <= next_y < w):
                if arr[next_x][next_y] == 1:
                    arr[next_x][next_y] = 0
                    queue.append((next_x, next_y)) 

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w * h == 0:
        break
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1:
                cnt += 1
                arr[i][j] = 0
                BFS(i,j)
    print(cnt)

1.  arr[i][j]이 1이면 섬이기 때문에 일단 갯수를 올려주고 0으로 만들고(재방문하지않기위해) 이 섬과 인접해있는 모든 섬들을 다 0으로 만들어줄거다(BFS함수내에서). 8개의 방향을 다 돌면서 1이면 queue에 넣고 그 섬과 인접한 섬을 또 queue에 넣고 이런식으로 접해있는 모든 섬을 0으로 만들면서 진행한다.

깨달은 점

• 분명 어떻게 짤지 다 알겠는데도 어떻게 짤지 모르겠다 ㅋ ㅋ 문제는 이해했는데 코드를 못짠다 -> 그럼 문제를 이해 못한겁니다 - 나OO 교수님 - . . . 새겨듣도록 하겠습니다....

문제

www.acmicpc.net/problem/2170

처음 작성한 코드

import sys

N = int(sys.stdin.readline())
line = []
for i in range(N):
    x, y = map(int, sys.stdin.readline().split())
    line.append((x, y))
line.sort(key=lambda x:x[0])

# 현재를 기준으로 그려진 선의 시작점(선의 시작)과 끝점(선의 끝)
s = line[0][0]
e = line[0][1]

result = e - s

for i in range(1, N):
    if line[i][0] <= e and line[i][1] <= e: # 현재 그은 선이 전에 그은 선에 완전히 겹칠때
        continue

    if line[i][0] <= e <= line[i][1]: # 일부만 겹칠때, 겹친부분 빼주기
        result += (line[i][1]-line[i][0]) -(e - line[i][0])
        e = line[i][1]
        s = line[i-1][0]
    else:
        result += line[i][1]-line[i][0]
        e = line[i][1]
        s = line[i][0]

print(result)

깨달은 점

• 처음에 조건을 일부 겹치는 때만 생각을 해서 코드를 짰는데 틀렸다고 나왔다.. 두번째는 현재 선이 이전 선과 완전히 겹쳐서 더하지 않아도 될때를 찾았는데도 틀렸다고 나왔다.. 왜냐면 s, e같은 시작, 끝점을 따로 안두고 바로 앞 i-1번째와 비교를 했기 때문이다.. 사람들은 너무 똑똑하다..

문제

www.acmicpc.net/problem/1744

처음 작성한 코드

import sys

def get_max(arr):
    result = 0
    for i in range(0, len(arr), 2):
        if i < len(arr)-1:
            result += arr[i] * arr[i+1]
        else:
            result += arr[i]
    return result

N = int(sys.stdin.readline())
positive = [] #1초과
negative = [] #0이하, 0은 음수가 하나일 때, 곱해지는게 이득
one = [] #1은 곱해지지않고 더해져야 더 큰 수가 나옴

for i in range(N):
    tmp = int(sys.stdin.readline())
    if tmp <= 0: negative.append(tmp)
    elif tmp > 1: positive.append(tmp)
    else : one.append(tmp)

negative.sort() # 작은 것부터 나열해서 곱하면 제일 커지는 방향
positive.sort(reverse=True) # 큰 것부터 나열해야 제일 커지는 방향

result = get_max(negative) + get_max(positive) + sum(one) # 1은 모두 더해줘야 제일 커짐

print(result)

1. 입력받은 수를 0이하인 수(negative), 1초과인 수(positive), 1인 수들(one)으로 나눈다.
2. 음수는 작은거를 두개 곱하면 더 큰 수를 만들 수 있으니 그냥 sort를, 양수는 큰거 두개를 곱해야 더 큰 수를 만들 수 있으니 reverse=True 옵션을 줘서 정렬했다.
3. 1은 곱하는 것보다 더하는게 더 큰 수를 만들 수 있으니 sum(one)을 통해 입력받은 모든 1을 더해주도록 했다.

깨달은 점

• 이 문제는 그리디를 이용하여 푸는 문제라고 한다. 그리디 잘 모르겠다. 현재 상태에서 제일 좋은 걸 고르면 된다고 하는데 나는 그것도 모르고 현 상태 아니고 모든 상태에서 젤 좋은 값 구하려고 if문을 9138234개 정도 쓰면서 2시간을 날렸다 ㅋㅋ 재밌넹

문제

www.acmicpc.net/problem/2668

처음 작성한 코드

import sys

N = int(sys.stdin.readline())
arr = {i:int(sys.stdin.readline()) for i in range(1, N+1)} 
visited = [False] * (N+1)
result = []

for i in range(1, N+1):
    tmp = []
    if not visited[i]:
        visited[i] = True
        tmp.append(i)
        while tmp:
            if not visited[arr[tmp[-1]]]:
                visited[arr[tmp[-1]]] = True
                tmp.append(arr[tmp[-1]])
            else:
                if tmp[0] == arr[tmp[-1]]:
                    for j in tmp:
                        result.append(j)
                else:
                    for j in tmp:
                        visited[j] = False
                tmp = []

print(len(result))
for i in sorted(result):
    print(str(i))

예제 입력을 기준으로 설명하겠다.

1. 1->3, 3->1 이면 루프가 생기고 이런 루프가 생기면 result에 넣는 방식으로 작성. 5->5도 루프가 생기니까 result에 넣음
2. while문 안에 첫 if-else 문은 현재 번호와 연결되어있는 번호가 방문이 되어있는지를 체크한다. 만약 방문이 안됐으면 방문됐다고 체크하고 tmp에 연결되어있는 번호를 넣는다. 이렇게 계속 하다보면 연결되어있는 모든 노드를 계속 들어가면서 방문하게 된다.
3. else(연결되어있는 번호가 이미 방문됐다면)를 만나서 만약 시작점과 지금 가려는 번호(방문되었다고 체크되서 else로 빠진 번호)가 같으면 루프를 생성하니까 result에 tmp에 있는 번호를 다 넣는다. ex) 1->3->1(arr[tmp[-1]])일때 tmp[0](시작점)과 arr[tmp[-1]](지금 가려던 번호)가 같으니 tmp에 있는 1과 3을  result에 넣는다.
4. 만약 시작번호와 지금 번호가 같지 않다면 방문되어있다는 걸 다시 false로 바꿔줘야 그 뒤 진행을 다시 할 수 있다. ex) 4->5->5 일때 4와 5를 visited false로 해줘야 5->5일때를 잡을 수 있다 왜냐면 제일 큰 for 문에서 not visited상대로만 진행하기 때문에..

코드 리뷰 후

import sys

def DFS(i, start):
    visited[i] = True

    if not visited[arr[i]]:
        DFS(arr[i],start)
    elif visited[arr[i]] and arr[i] == start:
        result.append(i)


N = int(sys.stdin.readline())
arr = {i:int(sys.stdin.readline()) for i in range(1, N+1)}
result = []

for i in range(1,N+1):
    visited = [False] * (N+1)
    DFS(i,i)

print(len(result))
for i in sorted(result):
    print(i)

처음 작성한 코드를 재귀로 푼 모습이다!

깨달은 점

• 마지막에 출력할 때 for문 돌면서 프린트하는 걸 까먹어서 '\n'.join(result)이런식으로 했는데 결과는 똑같던데 백준에서는 틀렸다고 해서 그거때문에 시간 날렸음!!!
• 생각하는데 오래걸리지 않았는데 구현하는데 오래걸렸다 왤까?

문제

www.acmicpc.net/problem/14719

처음 작성한 코드

import sys

h, w = map(int, sys.stdin.readline().split())

block = list(map(int, sys.stdin.readline().split()))
rain = 0

for i in range(w):
    left_max = max(block[:i+1])
    right_max = max(block[i:])
    point = min(left_max,right_max)
    rain += abs(point - block[i])

print(rain)

1. 자신을 포함한 왼쪽에서 제일 높은 블럭을 구한다.
2. 자신을 포함한 오른쪽에서 제일 높은 블럭을 구한다.
3. 1번과 2번에서 구한 블럭 중 더 낮은 블럭을 구한다. 이를 기준으로 빗물이 고일 것이기 때문
4. 현재 인덱스와 더 낮은 블럭(3번에서 구한 블럭)과의 차이를 더해준다.

깨달은 점

• 사실 다른 분 코드 보고 짰다.. 처음에 생각한 방법은 현재 인덱스에서 오른쪽으로 가면서 나보다 높은 블럭을 만나기 전까지 만났던 블럭들의 차이를 더해주는 식으로 짜려고 했는데 생각해보니 그럼 나보다 낮은 애들이 나오면 어쩌지? 라는 생각에 계속 정체됐던 것 같다.. 사람들은 너무 똑똑행!