그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 문제를 잘 읽어봐야 한다. 한번 기울이게 되면 빨간공이랑 파란공 둘다 벽에 부딪히거나 구멍에 들어갈때까지 그 방향 끝까지 가야 함.
2. 두개의 공 모두 벽이나 구멍을 만날때까지, 혹은 공끼리 부딪힐때까지 파란공과 빨간공을 네가지 방향으로 이동시켜 본다. (위, 아래, 왼쪽, 오른쪽)
   1. 이 때, 빨간공이 구멍에 들어가고, 파란공이 구멍에 들어가지 않는다면 정답이므로 이동 거리를 출력한다.
   2. 파란공이 구멍에 들어가게 되면 틀린것이므로 해당 방향으로 이동한 케이스는 큐에 삽입하지 않는다.
   3. 공이 부딪히게 되는 경우, 공의 위치를 잘 조정해주어야 한다. - 이부분 틀려서 시간 오래 걸림.
3. 두개의 구멍 모두 들어가는 케이스는 정답이 아닌 것이므로 해당 케이스도 큐에 삽입하지 않는다.
4. 이동거리가 11 이상인 경우 -1 출력하고, 나머지 경우 이동거리를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda : sys.stdin.readline().rstrip()

N, M = map(int, input().split())

matrix = [list(input()) for _ in range(N)]

b_pos = [0, 0]
r_pos = [0, 0]
for i in range(N):
    for j in range(M):
        if matrix[i][j] == 'B':
            b_pos[0], b_pos[1] = i, j
            matrix[i][j] = '.'
        if matrix[i][j] == 'R':
            r_pos[0], r_pos[1] = i, j
            matrix[i][j] = '.'

def bfs(matrix, bpos, rpos):
    queue = deque([[bpos[0], bpos[1], rpos[0], rpos[1], 1]])
    N, M = len(matrix), len(matrix[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    visited = set([(bpos[0], bpos[1], rpos[0], rpos[1])])
    while queue:
        b_x, b_y, r_x, r_y, cost = queue.popleft()
        b_pos,r_pos = [b_x, b_y], [r_x, r_y]
        if cost == 11:
            break
        for i in range(4):
            bx, by = b_pos
            rx, ry = r_pos
            b_finish, r_finish = False, False
            b_end, r_end = False, False
            while True:
                # 벽을 만날때까지 파란 공 이동
                if matrix[bx + dx[i]][by + dy[i]] != '#':
                    bx, by = bx + dx[i], by + dy[i]
                else:
                    b_end = True

                # 벽을 만나거나 구멍을 만날때까지 빨간 공 이동
                if matrix[rx + dx[i]][ry + dy[i]] != '#' and not r_finish:
                    rx, ry = rx + dx[i], ry + dy[i]
                else:
                    r_end = True

                # 빨간공과 파란공이 만났을 때
                if rx == bx and ry == by:
                    if r_finish: # 빨간색이 구멍에 들어간 경우 파란공도 들어가는 것
                        b_finish = True
                    # 이미 빨간공이 멈춰선 경우 파란공 위치 조정
                    if r_end:
                        bx, by = bx - dx[i], by - dy[i]
                    # 이미 파란공이 멈춰선 경우 빨간공 위치 조정
                    elif b_end:
                        rx, ry = rx - dx[i], ry - dy[i]
                    break

                # 파란공이 구멍에 들어간 경우 finish 처리
                if matrix[bx][by] == 'O':
                    b_finish = True
                    break
                
                # 빨간공이 구멍에 들어간 경우 finish 처리
                if matrix[rx][ry] == 'O':
                    r_finish = True

                # 둘다 벽을 만난 경우 종료
                if b_end and r_end:
                    break
                
            # 빨간공은 들어가고 파란공은 들어가지 않은 경우 거리 리턴
            if r_finish and not b_finish:
                return cost

            # set에 방문기록 저장 (재방문하지 않도록)
            if (bx, by, rx, ry) not in visited and not b_finish:
                visited.add((bx, by, rx, ry))
                queue.append([bx, by, rx, ry, cost+1])

    return -1

print(bfs(matrix, b_pos, r_pos))

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

풀이 과정

1. 최대 집하장의 개수가 200개이기도 하고, 각각의 집하장에서 가장 먼저 거쳐야 하는 집하장을 구해야 하므로 다익스트라 알고리즘보다는 플로이드 알고리즘이 더 괜찮아 보인다.
2. 최단 경로를 구하는 것이 아닌, 어디를 거쳐야 하는지를 구해야 하므로, 플로이드 알고리즘으로 거리를 갱신하면서 갱신할때 거치는 노드를 따로 저장해 둔다.
3. 마지막으로, 플로이드 알고리즘을 사용하면 가장 마지막에 거쳐가는 노드를 저장하므로, 이를 타고 올라가서 가장 먼저 거쳐야 하는 집하장을 구하여 저장해 둔다.
4. 저장해 둔 전체 경로표를 출력시켜 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

INT_MAX = int(10e9)
n, m = map(int, input().split())

matrix = [[INT_MAX] * (n+1) for _ in range(n+1)]
answer = [[0] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    matrix[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    matrix[a][b] = min(matrix[a][b], c)
    matrix[b][a] = min(matrix[b][a], c)
    answer[a][b] = b
    answer[b][a] = a


# 최단거리 구하는 파트
# 최단거리 구하면서 거리 갱신 시 어느 노드를 들리는지 정보 저장
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            if matrix[j][k] > matrix[j][i] + matrix[i][k]:
                matrix[j][k] = matrix[j][i] + matrix[i][k]
                answer[j][k] = i

# 다른 노드를 들리게 되는 경우,
# 거슬러 올라가서 가장 먼저 거쳐야 하는 집하장으로 바꾸어 줌
for i in range(1, n+1):
    for j in range(1, n+1):
        if answer[i][j] == 0:
            answer[i][j] = '-'
            continue
        p = answer[i][j]
        while p != answer[i][p]:
            p = answer[i][p]
        answer[i][j] = p

for a in answer[1:]:
    print(*a[1:])

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

풀이 과정

1. 일반적인 BFS 문제들과 비슷
   • 현재 0의 위치가 X,Y라고 할 때, 0의 위치로 이동할 수 있는 점은 (X-1,Y)에서, (X, Y-1)에서, (X+1, Y)에서, (X, Y+1)에서 총 네가지 경우라고 볼 수 있음. 물론 배열의 범위를 벗어나게 되는 경우는 제외해야 함.
2. 어려웠던 점은.. 메모리 초과 문제
   • 한번 방문했던 지점을 다시 방문하지 않도록 하기 위해 저장을 해야 하는데, 방문한 2차원 배열을 그대로 저장하면 메모리 초과 문제가 나타남.
   • 따라서, 방문 기록과 큐에 저장할 때 문자열 형태로 저장, 예시로 [[1,2,3], [4,5,6], [7,8,0]]인 경우, 123456780으로 저장한 다음, 큐에서 꺼낼 때 다시 2차원 배열 형태로 바꿔줌.
3. 데이터를 저장할 때는 메모리를 최대한 아끼는 쪽으로 저장해야 됨.

소스 코드

import sys
import copy
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

matrix = [list(map(int, input().split())) for _ in range(3)]

def find_0(matrix):
    for i in range(3):
        for j in range(3):
            if matrix[i][j] == 0:
                return [i, j]
    return None

def check_finish(matrix):
    answer = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    for i in range(3):
        for j in range(3):
            if answer[i][j] != matrix[i][j]:
                return False
    return True

def atos(matrix):
    result = ''
    for i in range(3):
        for j in range(3):
            result += str(matrix[i][j])
    return result

def stoa(string):
    return [[int(string[3*i+j]) for j in range(3)] for i in range(3)]

def bfs(matrix):
    visited = set([atos(matrix)])
    queue = deque()
    queue.append([atos(matrix), 0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        mat, movement = queue.popleft()
        mat = stoa(mat)
        if check_finish(mat):
            return movement
        x, y = find_0(mat)
        for i in range(4):
            target_x = x + dx[i]
            target_y = y + dy[i]
            if target_x >= 0 and target_x < 3 and target_y >= 0 and target_y < 3:
                mat[x][y], mat[target_x][target_y] = mat[target_x][target_y], mat[x][y]
                if atos(mat) not in visited:
                    visited.add(atos(mat))
                    queue.append([atos(mat), movement+1])
                mat[x][y], mat[target_x][target_y] = mat[target_x][target_y], mat[x][y]
    
    return -1

print(bfs(matrix))

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

풀이 과정

• 이전 문제랑 크게 다르지 않은듯 하면서 많이 다른 문제.. split을 쓰는것보다는 직접 진행하는것이 훨씬 쉽게 풀었던 것 같음.. 이전 문제가 더 쉬웠는데 왜 이번 문제가 정답률이 높지??..

1. 왼쪽에서 진행하면서 '<' 문자를 만났을 때와 안만났을 때로 구분한다.
   • '<' 문자를 만났을 때
     • 이전 스택에 저장되어있던 문자를 모두 pop해주면서 저장 (이전 문자는 뒤집힘)
     • 문자를 그대로 저장
   • '<' 문자를 만나지 않았을 때
     • 문자를 스택에 저장
2. 공백을 만나게 되면(' ')
   • '<>' 내부라면 그냥 저장해주면 된다.
   • '<>' 내부가 아니라면 공백을 만나기 전까지 스택에 저장된 문자들을 모두 pop해주면서 저장하고, 공백을 뒤에 붙여준다.
3. 맨 마지막에, 스택에 문자가 남아있다면 모두 pop해준 다음 저장해둔다.
4. 저장해둔 문자를 출력한다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

sentence = input()
stack = []
skip = False
answer = ''
for ch in sentence:
    if ch == '<':
        while stack:
            answer += stack.pop()
        skip = True
    elif ch == '>':
        answer += '>'
        skip = False
        continue

    if skip:
        answer += ch
    else:
        if ch == ' ':
            while stack:
                answer += stack.pop()
            answer += ch
        else:
            stack.append(ch)

while stack:
    answer += stack.pop()

print(answer)

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

풀이 과정

1. 입력받은 문장을 공백 기준으로 단어별로 쪼갠다.
2. 각 단어별로 진행하면서 알파벳을 순서대로 스택에 넣는다
3. 다시 스택에서 빼주면 알파벳이 뒤집어진 단어가 나온다.
4. 단어들을 붙여서 출력해주면 된다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T):
    sentence = input().split()
    stack = []
    for word in sentence:
        convert = ''
        for ch in word:
            stack.append(ch)
        while stack:
            print(stack.pop(), end="")
        print(" ", end="")
    print()

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

풀이 과정

1. 문제를 간단하게 생각하면 이진 탐색으로 위치를 찾으면 왼쪽 구간의 요소의 개수가 바로 먹을수 있는 수이다. 
   • 즉, 이진 탐색 결과가 곧 개수이다.
2. A의 각각의 요소들을 리스트 B에 대해서 이진탐색 진행
   • 같은 경우 왼쪽 구간 진행(같아도 안되므로)
   • 파이썬의 bisect_left 함수 사용
3. 요소의 개수의 합을 출력해주면 된다.

소스 코드

import sys
from bisect import bisect_left

input = lambda : sys.stdin.readline().rstrip()

T = int(input())

for _ in range(T):
    A, B = map(int, input().split())
    T1 = sorted(map(int, input().split()))
    T2 = sorted(map(int, input().split()))
    count = 0
    for e1 in T1:
        pos = bisect_left(T2, e1)
        count += pos
    print(count)

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

풀이 과정

1. 오목판의 왼쪽 위에서 아래쪽으로 진행하면서 전체 경우의 수를 탐색하면 된다.
   • 왼쪽 위에서 아래로 진행하므로, 위쪽 방향으로는 조사할 필요 없이 아래 방향으로만 조사하면 된다.
2. 단, 6개 이상의 돌이 연속으로 있는 경우는 안되므로 (0, 0)에서 (5, 5)까지 6개가 있는걸 (1, 1)에서부터 시작해서 (5, 5)까지 5개가 있는걸로 잘못 처리되는걸 방지하기 위해 visited 배열을 따로 둔다.
   • visited 배열의 경우는 [19][19][4] 형식으로 구성. 4는 왼쪽아래 대각, 아래, 오른쪽아래 대각, 오른쪽 총 4개의 방향으로 방문 가능하므로 3차원 배열로 구성
   • 이미 방문한 경우는 재방문하지 않도록 처리
3. 전체 경우의 수를 돌면서 오목인 경우, 해당 위치와 돌의 종류를 출력시켜주면 된다.
   • 예외사항으로, 왼쪽아래 대각 방향이 정답인 경우는 가장 왼쪽 돌을 출력해주라고 하였으므로 현재 위치 기준 x+4, y-4 해주면 된다.

소스 코드

import sys

input = lambda :sys.stdin.readline().rstrip()

matrix = [list(map(int, input().split())) for _ in range(19)]
visited = [[[False] * 4 for _ in range(19)] for _ in range(19)]

def check(matrix, visited, x, y):
    direction = [[1, -1], [1, 0], [0, 1], [1, 1]]
    p = matrix[x][y]

    for idx, d in enumerate(direction):
        temp_x, temp_y = x, y
        if visited[temp_x][temp_y][idx]:
            continue
        visited[temp_x][temp_y][idx] = True
        count = 1
        while True:
            temp_x, temp_y = temp_x + d[0], temp_y + d[1]
            if 0 <= temp_x and temp_x < 19 and 0 <= temp_y and temp_y < 19:
                if matrix[temp_x][temp_y] == p:
                    visited[temp_x][temp_y][idx] = True
                    count += 1
                else:
                    break
            else:
                break
            if count >= 6:
                break

        if count == 5:
            if d[0] == 1 and d[1] == -1:
                return [x+4, y-4]
            return [x, y]
        
    return None

end = False
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] != 0:
            result = check(matrix, visited, i, j)
            if result is not None:
                i, j = result
                print(matrix[i][j])
                print(i+1, j+1)
                end = True
        if end:
            break
    if end:
        break

if not end:
    print(0)

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

풀이 과정

1. 수열의 왼쪽에서부터 순차적으로 진행한다.

   • 현재의 숫자가 존재하지 않는다면 큐에 넣어준다.
   • 현재의 숫자가 큐에 존재한다면, 현재 숫자가 나올때 까지 큐에서 빼내준 다음 현재 숫자를 넣는다.

2. 현재 큐의 길이를 따로 저장해 둔다.

   • 이유는 현재 숫자가 5고, 큐에 [2, 3, 5]가 들어있다면 경우의 수는 [2, 3, 5], [3, 5], [5] 3가지 즉, 큐의 길이만큼의 경우의 수가 나올 수 있다.

3. 저장해둔 큐의 길이의 합계를 출력해주면 된다

   • 전체 경우의 수를 구해야 하므로

소스 코드

import sys
from collections import deque

input = lambda : sys.stdin.readline().rstrip()

n = int(input())
sequence = list(map(int, input().split()))

dp = [0] * len(sequence)
queue = deque()
current = set()
for i in range(len(sequence)):
    if sequence[i] in current:
        while queue:
            pos, value = queue.popleft()
            current.remove(value)
            if value == sequence[i]:
                break
    queue.append([i, sequence[i]])
    current.add(sequence[i])

    dp[i] = len(current)

print(sum(dp))

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

풀이 과정

• 처음엔 그냥 무식하게 탐색으로 하려고 했으나 계속 시간초과가 나옴.

  • 생각해보니 최대 1000개 학급에 최대 1000명의 학생이 가능한데 조건을 걸더라도 1000의 1000제곱은 풀릴리가 없음,,

• 고민하다 찾아보니 투포인터 알고리즘을 사용한다고 해서 투포인터 알고리즘으로 풀이

  • 모든 각각의 학급 내 학생들을 오름차순으로 정렬한 후, 초기에는 각 학급에서 능력치가 가장 낮은 학생들만 뽑아서 그룹을 만든다.
  • 차이를 좁히기 위해서는 최솟값을 올리던지 최댓값을 내리던지 해야 하는데.. 능력치가 낮은 학생에서 높은 학생 순으로 진행하므로 최댓값을 내릴수 없으므로 최솟값을 올리는 방식만 고려하면 된다.
  • 최소 히프를 사용해서 능력치가 가장 낮은 학생을 뽑고, 그 학생이 속한 그룹의 다음 학생을 다시 히프에 넣어주는 방식으로 진행
  • 과정 중에 하나의 반의 마지막 학생이 최솟값인 경우 더이상 최솟값을 갱신할 수 없으므로 종료하면 된다.
  • 과정 중 최댓값과 최솟값의 차이는 계속해서 갱신해준다.

소스 코드

import sys
import heapq
from collections import deque

input = lambda : sys.stdin.readline().rstrip()

n, m = map(int, input().split())
students = [deque(sorted(list(map(int, input().split())))) for _ in range(n)]

heap = []

min_value = int(10e9)
max_value = 0

for i in range(len(students)):
    v = students[i].popleft()
    max_value = max(max_value, v)
    min_value = min(min_value, v)
    heapq.heappush(heap, [v, i])

sumation = max_value - min_value

while heap:
    prev_min_value, pos = heapq.heappop(heap)
    if not students[pos]:
        # 해당 deque가 비어있다면 더이상 갱신 불가능
        break

    new_value = students[pos].popleft()
    heapq.heappush(heap, [new_value, pos])

    if max_value < new_value:
        max_value = new_value
    min_value = heap[0][0]
    sumation = min(sumation, max_value - min_value)


print(sumation)

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

풀이 과정

1. 입력받은 친구 번호에 맞추어서 그래프를 구성한다.

   • graph[번호]에 해당 번호의 친구들을 저장해둔다.

2. 1번부터 DFS를 진행하여 결혼식에 오는 친구들을 방문처리 해준다.

   • DFS의 깊이가 2일때 종료시켜 준다. (친구의 친구까지만 진행하므로)

3. 전체 DFS 과정이 종료되면 VISITED가 TRUE인 개수를 구한 뒤 1을 빼준다.

   • 상근이를 빼주어야 함.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

def dfs(graph, visited, person, depth):
    if depth == 2:
        return
    for nx in graph[person]:
        if not visited[nx]:
            visited[nx] = True
        dfs(graph, visited, nx, depth+1)

n = int(input())
m = int(input())
friends = [map(int, input().split()) for _ in range(m)]

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
visited[1] = True

for p1, p2 in friends:
    graph[p1].append(p2)
    graph[p2].append(p1)

dfs(graph, visited, 1, 0)
print(len(list(filter(lambda x:x==True, visited))) - 1)