구름톤 챌린지가 모두 끝났다. 블록 20개 모두 완성!!

모두 완주해서 기분이가 좋다ㅎㅎ 내캐릭터도 완주한 기념으로 트로피를 들고있다. 매일 아침마다 잠도 깰겸 풀었는데 이제 오전시간때 뭐해야 될지 고민이 된다...

18일차 : 중첩 점

import sys
input = sys.stdin.readline

# 가로선, 세로선 그리는 함수
def draw_line(r,c,d):
    dx, dy = direction[d]
    while True:
        # 인덱스 범위 넘어가면 반복문 탈출
        if r < 0 or c<0 or r >= n or c >= n:
            break
        
        if d == 'L' or d == 'R':
            graph[r][c][0] += 1
        elif d == 'U' or d == 'D':
            graph[r][c][1] += 1

        r += dx
        c += dy
            
# n행열, m 직선 개수
n, m = map(int, input().split())

direction = {"U": (-1,0), "D":(1,0), "L":(0,-1), "R":(0,1)}

#(가로, 세로) 값 저장
graph = [[[0,0] for _ in range(n)] for _ in range(n)]

# 반직선 입력 받기
for _ in range(m):
    # 행, 열 좌표, 방향
    r, c, d = map(str, input().split())
    r, c = int(r) -1, int(c) - 1
    # 그래프에 가로 개수, 세로 개수 저장함!
    draw_line(r, c, d)

# 출력
cnt = sum(graph[i][j][0] * graph[i][j][1] for i in range(n) for j in range(n))
print(cnt)

요약하자면 한 칸에 점이 생기려면 가로선과 세로선이 있어야 점이 하나 생긴다. 가로선 갯수 X 세로선 갯수 = 중첩점 개수가 된다.

graph 리스트를 생성해 해당 칸의 [가로선 개수, 세로선 개수]를 저장하며, d방향으로 인덱스 범위가 초과 되지 않을 때까지 이동하며 세로나 가로선을 갱신 해준다.

최종적으로 모든 리스트 내부를 돌며 가로개수 * 세로개수를 모두 더하면 총 중첩 점의 개수가 된다.

스터디 팀원 분 중에 마지막 테스트 케이스가 통과 되지 않아서 같이 고민했었는데 자료형 범위를 초과해서 그런 것이였다. 반직선의 개수가 1<=M<=100,000 이니까 한 행과 한 열에 50,000, 50,000개씩 있게 되면 중첩점은 25억개가 되어버리니까 자료형 타입이 있는 언어는 주의해서 풀어야 한다.

19일차 : 대체 경로

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

def bfs(graph, s, e, repair_city):
    # 시작 도시나 끝 도시가 공사중이라면 - 1
    if s == repair_city or e == repair_city:
        return -1

    # 공사할 도시가 매일 바뀌기 떄문에 내부에 visited 생성함
    visited = [False] * (n+1)

    # 도시와 방문한 도시 수
    q = deque([(s, 1)])
    visited[s] = True

    while q:
        city, cnt = q.popleft()

        # 목적지에 도달했는지 확인
        if city == e:
            return cnt
        
        for next_city in graph[city]:
            # 아직 방문하지 않고, 수리중인 도시가 아니라면 큐에 삽입
            if not visited[next_city] and next_city != repair_city:
                visited[next_city] = True
                q.append((next_city, cnt+1))

    # 모두 순회해도 목적지에 도달할수 없는 경우
    return -1

# 도시수, 도로수, 출발노드, 도착 노드
n, m, s, e = map(int, input().split())

# 인접리스트 방식인데 딕셔너리로 구현해봄
# 리스트로 구현한거랑 시간복잡도차이는 거의 없을듯 둘다 접근 O(1) 시간복잡도니까
graph = {i : [] for i in range(1, n+1)}

# 간선 입력받기
for _ in range(m):
    u, v = map(int,input().split())
    # 도시 양방향으로 연결
    graph[u].append(v)
    graph[v].append(u)

for i in range(1, n+1):
    print(bfs(graph, s, e, i))

최단 경로는 그래프에 가중치가 없을때에는 BFS!! 있을 때는 다익스트라!! 그렇다면 BFS가 어떻게 최단 경로를 보장할까?

정답은 BFS가 노드를 방문하는 순서에 있다. 시작노드에서부터 인접한 다음 계층 노드를 차례대로 방문한다.(거리가 +1) 탐색한 후 거리가 시작노드로 부터 2인 모든 노드 탐색... (반복)

글로 설명하면 어려우니 그림으로 보자면

A부터 F까지의 최단경로를 알아보고싶다. 물론 눈으로 보면 2다!! 하지만 동작 방식을 알고싶다!

시작노드는 A를 큐에 넣고 방문처리한다.

그리고 A를 큐에서 꺼내고 인접한 노드 B, C를 큐에넣고 방문처리한다.(보면 시작 노드와 거리가 1이다.)

B, C 순서로 넣었으니 B를 꺼내고 D를 큐에 넣고 방문처리한다. (시작노드와 거리 2)

그리고 다음 순서인 C를 큐에서 꺼내고, 인접한 노드 E, F를 큐에 넣고 방문처리한다. (시작노드와 거리2)

이제 규칙이보이는가? 시작노드와 거리가 1인것들을 모두 방문하고 그다음 시작노드에서 거리가 2인 것들을 모두 방문한다.
결론 : BFS는 시작노드로 부터 거리가 1인 노드 부터 탐색 후, 거리가 2인 모든 노드를 탐색한다. 이런식으로 계속반복 되기 때문에 해당 노드를 처음 방문한다면, 이 노드의 거리는 시작노드로 부터 최단경로 인 것이다.

만약 해당 노드를 방문했는데 더 짧은 경로가 있다면 BFS가 이전에 이미 방문한 노드일 것이다. 때문에 방문한 노드는 다시 방문하지 않도록 처리해줘야한다.

20일차 : 연결 요소 제거하기

import sys
from collections import deque
input = sys.stdin.readline
 
n, k, q = map(int,input().split())

graph = [list(input().strip()) for _ in range(n)]

# 삽입할 문자 입력 받기
inputStr = [list(input().split()) for _ in range(q)]


def bfs(x, y, graph):
    global n
    visited = [[False]*n for _ in range(n)]
    connectElments = [(x, y)]
    q = deque([(x, y)])
    visited[x][y] = True

    while q:
        i, j = q.popleft()
        # 상하 좌우 이동
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = i + dx, j + dy
            # 인덱스 범위 체크 및 방문체크 및 같은 문자인지체크
            if 0<= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] == graph[x][y]:
                visited[nx][ny] = True
                q.append((nx, ny))
                connectElments.append((nx,ny))
    return connectElments

for x, y, d in inputStr:
    x, y = int(x) - 1, int(y) - 1
    # x, y칸은 . 문자가 적힌 칸을 보장하기 때문에 그냥 삽입
    graph[x][y] = d

    # 삽입된 인접한 요소듦만 체크
    connectElments = bfs(x, y, graph)
    if len(connectElments) >= k:
        for i, j in connectElments:
            graph[i][j] = "."


for row in graph:
    print(''.join(row))

시뮬레이션 문제이다. (애니팡? 게임과 유사하다.)
1.(x,y)를 입력받아 그래프에서 해당하는 좌표를 d문자로 초기화 한다.
2.(x,y)는 .문자가 적힌 칸임을 보장하므로 그냥 삽입한다.
3.그리고 BFS로 d문자와 같은지 확인하고 같으면 연결요소에 추가해준다. (connectElments)
4.모두 탐색하고 connectElemnets의 크기가 K이상이면 connectElemnets에 해당하는 모든 문자를 .으로 변경한다.
5. 1~4를 q만큼 반복한다.

references

---

[그래프] 27. BFS로 찾은 경로가 최단 경로인 이유