코딩테스트 공부 1

같은 내용 다른 코드

 

 

def solution(emergency):
    answer = []
    dict = {}
    p = sorted(emergency, reverse = True)
    for i in range(len(emergency)):
        dict[p[i]] = i + 1
    for k in range(len(emergency)):
        answer.append(dict[emergency[k]])
    return answer

def solution(emergency):
    sorted_emergency = sorted(emergency, reverse=True)
    dict_emergency = {value: index + 1 for index, value in enumerate(sorted_emergency)}
    return [dict_emergency[value] for value in emergency]

def solution(emergency):
    return [sorted(emergency, reverse=True).index(e) + 1 for e in emergency]

 

 

 

 

dfs

import sys; input=sys.stdin.readline
N, M = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(N)]

result = 0


def dfs(x, y):
  if x < 0 or x >= N or y < 0 or y >= M:
    return False
  if graph[x][y] == 0:
    graph[x][y] = 1
    dfs(x-1, y)  
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)
    return True
  return False



for r in range(N):
  for c in range(M):
    if dfs(r, c) == True:
      result += 1

print(result)

 

 

DFS2

"""
1. 아이디어
- 2중 for, 값 1 && 방문X => DFS
- DFS를 통해 찾은 값을 저장 후 정렬 해서 출력

2. 시간복잡도
- DFS : O(V+E)
- V, E : N^2, 4N^2
- V+E : 5N^2 ~= N^2 ~= 625 >> 가능

3. 자료구조
- 그래프 저장 : int[][]
- 방문여부 : bool[][]
- 결과값 : int[]

"""

import sys
input = sys.stdin.readline

N = int(input())
map = [list(map(int, input().strip())) for _ in range(N)]
chk = [[False] * N for _ in range(N)]
result = []
each = 0
dy = [0,1,0,-1]
dx = [1,0,-1,0]

def dfs(y, x):
    global each
    each += 1
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0<=ny<N and 0<=nx<N:
            if map[ny][nx] == 1 and chk[ny][nx] == False:
                chk[ny][nx] = True
                dfs(ny, nx)

for j in range(N):
    for i in range(N):
        if map[j][i] == 1 and chk[j][i] == False:
            chk[j][i] = True
            each = 0
            dfs(j,i)
            result.append(each)

result.sort()
print(len(result))
for i in result:
    print(i)

 

 

 

 

 

백준 1926번 BFS 공부

import sys; input=sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(N)]

count = 0 #그림 개수
list_area = [0]  #넓이 리스트 기본은 0

def bfs (x, y):
  dx = [-1, 1, 0 , 0] # 상 하
  dy = [0, 0, -1, 1]  # 좌 우
  q = deque()  # 객체화
  q.append((x, y))  # 값 넣기
  graph[x][y] = 2 # 방문 상태를 '2'로 표현
  area = 1  # 기본 넓이는 1
  while q: # queue가 비어있지 않다면
    a, b = q.popleft()  # 왼쪽으로 2개 값을 꺼내서 a와 b로 지정(지정없으면 그냥 꺼내기만 하고 삭제됨)
    for i in range(4): # dx dy 길이가 4이므로 4
      nx = a + dx[i] # x좌표 상하좌우
      ny = b + dy[i] # y좌표 상하좌우
      if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1: 
        # 변경된 좌표가 그래프 안이고 방문 가능한 곳인 1이면
        area += 1 # 넓이 1개 추가
        graph[nx][ny] = 2 # 방문했다는 처리로 2로 지정
        q.append([nx,ny]) # nx ny로 q 집어넣기.
  list_area.append(area)      #넓이 리스트 업데이트

for x in range(N):
  for y in range(M):
    if graph[x][y] == 1: # 방문 가능한 곳이라면
      bfs(x,y) # bfs를 수행
      count += 1 # 개수 1

print(count)
print(max(list_area))

 

유사한 문제 1743 음식물 피하기

import sys; input = sys.stdin.readline
from collections import deque
N, M, K = map(int, input().split())
graph = [[0] * (M) for _ in range(N)]

for _ in range(K):
  r, c = map(int, input().split())
  graph[r-1][c-1] = 1 # index는 0부터 시작하므로 1을 빼줘야 한다!



list_area = [0]  #넓이 리스트 기본은 0

def bfs (x, y):
  dx = [-1, 1, 0 , 0] # 상 하
  dy = [0, 0, -1, 1]  # 좌 우
  q = deque()  # 객체화
  q.append([x, y])  # 값 넣기
  graph[x][y] = 2 # 방문 상태를 '2'로 표현
  area = 1  # 기본 넓이는 1
  while q: # queue가 비어있지 않다면
    a, b = q.popleft()  # 왼쪽으로 2개 값을 꺼내서 a와 b로 지정(지정없으면 그냥 꺼내기만 하고 삭제됨)
    for i in range(4): # dx dy 길이가 4이므로 4
      nx = a + dx[i] # x좌표 상하좌우
      ny = b + dy[i] # y좌표 상하좌우
      if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1: 
        # 변경된 좌표가 그래프 안이고 방문 가능한 곳인 1이면
        area += 1 # 넓이 1개 추가
        graph[nx][ny] = 2 # 방문했다는 처리로 2로 지정
        q.append([nx,ny]) # nx ny로 q 집어넣기.
  list_area.append(area)      #넓이 리스트 업데이트

for x in range(N):
  for y in range(M):
    if graph[x][y] == 1: # 방문 가능한 곳이라면
      bfs(x,y) # bfs를 수행
      
print(max(list_area))

 

 

 

 

백준 BFS 2178번 미로찾기

import sys; input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(N)] # strip을 사용!

dx = [ -1, 1, 0, 0]
dy = [ 0, 0, -1, 1]


queue = deque()
queue.append((0, 0, 1))  # 시작점이 있는 경우 미리 지정하고 시작한다. 3번째는 움직인 거리.

while len(queue) > 0:
  x, y, d = queue.popleft()
  if x == N-1 and y == M-1:    # 목적지 graph[N-1][M-1] 도달시 그냥 거리(d) 출력.
    print(d)
    break

  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    nd = d + 1    # 거리 1개씩 늘려나간다.
    if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
      queue.append((nx, ny, nd))
      graph[nx][ny] = 2   # 방문 처리

graph에서 split대신에 strip()을 해야 문제가 원하는대 제대로 인식이 된다.

 

 

 

 

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

BFS  알파벳 (deque대신 set을 사용)

import sys; input = sys.stdin.readline


N, M = map(int, input().split())
graph = [list(map(str, input().strip())) for _ in range(N)] # 알파벳이니 str로 받는다.
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


queue = set([(0, 0, graph[0][0])])  #set은 deque보다 시간복잡도가 작다. O(1)
answer = 1 # 지나온 길이를 잰다

while len(queue) > 0:
  x, y, block = queue.pop()  #set은 pop으로 한다.
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] not in block:
      queue.add((nx, ny, block + graph[nx][ny]))  
       # set은 add로 추가한다. 3번째 block은 문자열이 하나씩 길어진다.
      answer = max(answer, len(block)+1) #마지막 위치를 저장하기위해 +1

print(answer)

 

 

 

 

벽부수고 지나가기

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

import sys; input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 방문 배열: 3차원 배열 (x, y, 벽을 부순 횟수)
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]

# BFS 큐: (x, y, 벽을 부순 횟수)
queue = deque()
queue.append((0, 0, 0))


# BFS 탐색
while queue:
    x, y, wall = queue.popleft()

    # 목적지에 도달한 경우
    if x == N - 1 and y == M - 1:
        print(visited[x][y][wall] + 1)
        exit()  # 뒤에 코드 무시하고 바로 종료. 이거 없으면 -1 출력됨

    # 4방향 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        # 범위 검사
        if 0 <= nx < N and 0 <= ny < M:
            # 이동 가능하면서 방문하지 않은 곳인 경우
            if graph[nx][ny] == 0 and visited[nx][ny][wall] == 0:
            # visited[x][y][wall] + 1 = 현재 위치 + 1로 visited[nx][ny][wall]에 거리 저장.
                visited[nx][ny][wall] = visited[x][y][wall] + 1
                queue.append((nx, ny, wall))
            # 벽을 부수지 않은 상태에서 벽을 만난 경우
            elif wall == 0 and graph[nx][ny] == 1:
            # 벽을 부수므로 wall =1로 표현됨.
                visited[nx][ny][1] = visited[x][y][wall] + 1
                queue.append((nx, ny, 1))

# 도착지까지 도달하지 못한 경우
print(-1)

 

 

 

 

다이나믹 프로그래밍(1로 만드는 연산 횟수 최솟값)

import sys; input = sys.stdin.readline
X = int(input())
d = [0] * 300001

for i in range(2, X + 1):
  d[i] = d[i-1] + 1
  if i % 2 == 0:
    d[i] = min(d[i], d[i//2] + 1)
  if i % 3 == 0:
    d[i] = min(d[i], d[i//3] + 1)
  if i % 5 == 0:
    d[i] = min(d[i], d[i//5] + 1)

print(d[X])
print(d[0:X+1])

 

import sys; input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())
r, c, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

# d: 0 = north, 1 = east, 2 = south, 3 = west
q = deque()
area = 0

def back(d):
  if d == 0 and graph[x][y+1] != 1:
    return q.append((x, y+1, d))
  elif d == 1 and graph[x+1][y] != 1:
    return q.append((x+1, y, d))
  elif d == 2 and graph[x][y-1] != 1:
    return q.append((x, y-1, d))
  elif d == 3 and graph[x-1][y] != 1:
    return q.append((x-1, y, d))
  else:
    return -1



while q:
  q.append((r, c, d))
  x, y, d = q.popleft()

  if graph[x-1][y] == 2 and graph[x+1][y] == 2 and graph[x][y-1] == 2 and graph[x][y+1] == 2 and back(d) == -1:
    print(area)
    break
    
  elif graph[x-1][y] == 2 and graph[x+1][y] == 2 and graph[x][y-1] == 2 and graph[x][y+1] == 2 and back(d) != -1:
    back(d)