bright

import sys
sys.setrecursionlimit(10000000)

m, n, k = map(int, input().split()) # 세로 가로 직사각형 수 

# 직사각형으로 채워지면 1, 안 채워지면 0
graph = [ [0]*n for _ in range(m) ]

for i in range(k):
  s1, e1, s2, e2 = map(int,sys.stdin.readline().split())

  for x in range(s1,s2):
    for y in range(e1, e2):
      graph[y][x] = 1 

def dfs ( x, y, cnt ):
  graph[y][x] = 1 
  cnt += 1 

  move_x = [-1,1,0,0] # 가로 -> n 
  move_y = [0,0,-1,1] # 세로 -> m 

  for i in range(4):
    nx = x + move_x[i]
    ny = y + move_y[i]

    if nx < 0 or ny < 0 or nx >=n or ny>=m : 
      continue 
    if not graph[ny][nx] :
      cnt = dfs(nx,ny,cnt)
  
  return cnt

area = []

for x in range(n):
  for y in range(m):
    if not graph[y][x]:
      cnt = 0 
      area.append(dfs(x,y,cnt))

print( len(area) )
area.sort()
for i in range(len(area)):
  print(area[i], end=' ')

step 1 ) 런타임 에러 방지를 위해 sys import 하고  graph 선언 

           직사각형으로 채워질 부분은 1, 채워지지 않은 부분은 0 으로 설정한다. 

step 2 ) 직사각형의 좌표값을 입력받아 graph 채우기  -> 실제로 출력해보면 거꾸로 나오긴하는데 상관 없음 

step 3 ) dfs 구현, 가로 세로로 움직이면서 연결된 영역 세기 

           각 영역별 넓이를 구해야 하므로 dfs 가 진행 될 때마다 cnt 를 세어주고 return 하는 식으로 계산한다. 

step 4 ) graph 전체를 탐색하면서 dfs 를 진행한다. 이 때 돌려 받은 cnt 의 값을 각 구역의 넓이를 저장하는 area에 저장

step 5 ) area 의 길이와, 정렬한 결과를 출력

import copy
import sys
sys.setrecursionlimit(10000000)

n = int(input())

graph = []
max_h = 0 
for i in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))
  max_h = max( max_h, max(graph[i]))

save = [0] * ( max_h +1 )
save[0] = 1  # 비가 안오면 전 영역( 1개 ) 이 안전하다.

def dfs ( x,y,h, tmp_graph):

  move_x = [-1,1,0,0] # 가로 
  move_y = [0,0,-1,1] # 세로 

  tmp_graph[x][y] = 0 

  for i in range(4):
    nx = x + move_x[i]
    ny = y + move_y[i]

    if nx <0 or ny <0 or nx>=n or ny>= n : 
      continue 
    if tmp_graph[nx][ny] >= h : 
      dfs ( nx, ny, h, tmp_graph)

for h in range(1, max_h+1):
  tmp = copy.deepcopy(graph)
  cnt = 0 
  for i in range(n):
    for j in range(n):
      if tmp[i][j] >= h : 
        dfs(i,j,h,tmp)
        cnt += 1 
  save[h] = cnt 

print(max(save))

step 1 ) 그냥 입력 받으면 런타임 에러 나니까 import sys 

step 2 ) graph 입력 받기 , 가장 큰 높이 까지만 찾아보면 되니까 가장 큰 높이 구하기 

step 3 ) 각 높이 별 안전한 영역 저장할 list 선언 ( save ) 

           단, 높이가 0 일 때는 모두 다 하나의 안전한 구역이므로 1 로 설정. 

step 4 ) dfs 구현 하기. 가로 세로로 움직이며 다음과 같은 조건 부여

           ① 움직인 결과 그래프 안에 있는지  ② 현재 검사하고 있는 높이보다 높으면 dfs 진행 

            ③ 방문 처리를 위해서 dfs 진행한 구역은 값을 0으로 만들어주기 

step 5 ) 1 ~ 가장 높은 높이까지 반복.  기존 graph 는 바뀌면 안되니까 깊은 copy 를 통해 각 높이 별로 복사해서 사용 

           깊은 복사는 copy module 로 구현 가능하며,  a = copy.deepcopy( b ) 와 같이 쓴다. 

step 6 ) 각 높이 별 안전한 구역의 개수 세어서 저장, 가장 큰 값 출력하기 

import sys
sys.setrecursionlimit(10000000)

def island(w,h):

    graph = []
    for i in range(h):
      graph.append( list(map(int,sys.stdin.readline().split()))) 

    move_x = [ -1, 1, 0, 0, -1,-1,1,1 ]  # x는 세로, 순서대로 가로 세로 대각선 
    move_y = [ 0, 0, -1, 1, -1,1,-1,1 ]  # y는 가로
    
    def dfs ( x,y ) : 
        graph[x][y] = 0

        for i in range(8):
            nx = x + move_x[i]
            ny = y + move_y[i]

            if nx<0 or ny<0 or nx>=h or ny>=w :
              continue

            if graph[nx][ny] : 
              dfs( nx, ny )
              continue

    cnt = 0 

    for y in range(w):
      for x in range(h):
          if graph[x][y]:
            dfs(x,y)
            cnt += 1 
    return cnt 


p = []

while 1: 
    w, h = map(int,sys.stdin.readline().split()) # 지도 너비, 높이 <= 50 
    if w == 0 and h == 0 : 
        break 
    else:
        p.append( island(w,h) )

for i in range(len(p)):
  print(p[i])

거의 구현 문제다.. 

1. 섬과 바다 지도를 graph 에 받아오기 

2. 만약 내가 지금 방문한 노드가 섬이라면, 인접한 섬 방문하는 dfs 재귀 방법 사용 

   ( 인접한 섬을 방문하는 경우의 수는 가로 2개 세로 2개 대각선 4개하여, 총 8가지 이다. ) 

3. 한 번 탐색을 끝나면 섬 하나가 끝난 것이므로 cnt +1 

tip) 런타임 에러 해결 

-> 보토 입력값이 크고 파이썬은 조금 느린 언어다 보니까 입력하는 부분에서 런타임 에러가 발생할 수 있다. 

import sys

sys.setrecursionlimit(10000000)

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

위의 코드를 통하여 해결한다. ( 모든 입력 부분에 sys.stdin.readline() 을 사용한다 )

import sys
sys.setrecursionlimit(10000000)
n, m = map(int,sys.stdin.readline().split())

graph = [ [] for i in range(n+1) ]

for i in range(m):
  start, end = map(int,sys.stdin.readline().split())

  graph[start].append(end)
  graph[end].append(start)

visited = [False] * (n+1) 

def dfs ( graph, v,visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs( graph, i, visited)


cnt = 0 

for i in range(1,n+1):
  if not visited[i] :
    cnt += 1 
    dfs( graph, i, visited)

print(cnt)

그냥 아주 기초적인 bfs 풀이와 유사하다. 

프로그래머스의 네트워크 문제와 비슷한 것 같다. 

다만, 런타임 에러가 난다면 입력 할 때 sys를 import한 다음 아래 식을 사용해서 입력 받는다. 

import sys

sys.setrecursionlimit(10000000)

n, m = map(int,sys.stdin.readline().split())

DFS 

def dfs( v, visited_dfs ):
  if not visited_dfs[v-1] :
    visited_dfs[v-1] = True
    print(v, end=' ')
    
    if v in graph.keys():
      for i in graph[v]:
          dfs( i, visited_dfs )

1. 시작 노드를 stack 에 넣고 방문 처리 

2. stack의 최 상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 stack 에 넣고 방문 처리 

   -> 최 상단 노드 중 방문하지 않은 인접 노드가 없으면 최상단 노드 pop 

3. 반복 

BFS 

def bfs( v, visited_bfs ) :
    queue = deque()
    queue.append(v)

    while queue : 
        now = queue.popleft()

        if not visited_bfs[now-1]:
          visited_bfs[now-1] = True
          print(now, end= ' ')

          if now in graph.keys():
            for i in graph[now]:
              queue.append(i)

1. 탐색 시작 노드를 큐에 넣고 방문 처리

2. 큐에서 노드를 꺼내어 해다 노드의 인접 노드 중 방문하지 않은 모든 노드를 큐에 삽입 하고 방문 처리

3. 반복 

실행 코드 

from collections import deque 

n, m, v = map(int,input().split()) # 노드, 간선, 시작점 

graph = dict()

for i in range(m):
    start, end = map(int,input().split())

    if start in graph:
        graph[start].append(end)
    else:
        graph[start] = [end] 

    if end in graph:
      graph[end].append(start)
    else:
      graph[end] = [start]

for i in graph.keys():
    graph[i].sort()

visited_dfs = [False] * n
visited_bfs = [False] * n  

dfs(v, visited_dfs)
print()
bfs(v, visited_bfs)

개념만 알면 풀 수 있는 문제일 줄 알았는데 생각보다 오래 걸렸다. 

그래프 만들 때, start-end 와 end-start  모두 넣어 주어야 하는 것에 유의하자. 

www.acmicpc.net/problem/1260

def solution(tickets):

    routes = dict()

    for t1, t2 in tickets:
        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]
    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    st = ['ICN']
    ans = []
    while st:
        top = st[-1]
        if top not in routes or len(routes[top])==0:
            ans.append(st.pop())
            
        else:
            st.append(routes[top].pop())

    ans.reverse()
    return ans

... 아직 dfs-bfs 가 익숙하지 않다.  엄청 어렵다. 

step 1 ) 갈 수 있는 경로를 정의 한 routes 딕셔너리를 만든다. 

step 2 ) 문제에서 가능한 알파벳 순으로 나열하라고 했으므로 정렬한다. 이 때, 역으로 정렬하여 pop 했을 때 

           알파벳 순서가 빠른 곳이 먼저 나오도록 한다. 

step 3 ) 시작점은 'ICN' 이다. 

step 4 ) 문제에서 무조건 다 사용할 수 있다고 했으므로, 다음과 같은 알고리즘을 적용할 수 있다. 

           만약 내가 가려는 곳이 routes 에 존재하지 않는다면 ans 에 넣는다. 마지막에 다른 곳에서 이곳에 도착할 

           것이 분명하다.  존재한다면 다음 목적지로 삼으면 된다. 

Reference 

아래 블로그를 참고했음. 설명이 잘 되어있다. 

https://gurumee92.tistory.com/165

x, y = map(int,input().split()) # 월 일 

month = [0,31,28,31,30,31,30,31,31,30,31,30,31]

day = [ 'SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT' ]

today = 0 

for i in range(1,x):
  today += month[i]

today += y 

print ( day[today%7] )

n = input()
n = n.upper() 

cnt = [0] * 28 

for i in n :
  cnt [ ord(i)-65 ] += 1 

tmp = sorted(cnt)

if tmp[-1] != tmp[-2]:
  print( chr( cnt.index(tmp[-1]) +65 ))
else:
  print("?")

www.acmicpc.net/problem/1157

n = list(map(int,input()))
left, right = 0, 0

for i in range( len(n)//2 ):
  left += n[i]
  right += n[ len(n)-i-1 ]

if left == right :
  print("LUCKY")
else:
  print("READY")

# 시간초과 

n, m = map(int,input().split()) # 나무의 수, 필요한 길이 

trees = list(map(int,input().split()))

h = max(trees)

for i in range(h,0,-1):
  total = 0 
  for j in trees:
    if i < j : 
      total += j-i 
  
  if total >= m : 
    print(i)
    break

문제에서 나무의 최대값 이 매우 크게 잡혀 있는 것을 볼 수 있다. 

이렇게 그냥 풀면 당연히 시간초과가 나온다. 

# 정답 

n, m = map(int,input().split()) # 나무의 수, 필요한 길이 

trees = list(map(int, input().split()))
start, end = 1, max(trees)

while start <= end:
    mid = (start+end) // 2
    
    result = 0 
    for i in trees:
        if i >= mid:
            result += i - mid
    
    if result >= m:
        start = mid + 1
    else:
        end = mid - 1
print(end)

이분탐색을 적용하여 시간을 줄여야 한다. 

python3 로는 계속 시간초과 오류가 나서 pypy3 로 제출했다 : (