[수업기록] 알고리즘 : 문제풀이

240816

1. 삼성시의 버스 노선

SW Expert Academy

#의문점
#1. p, n이 대체 뭐지?
# -> p 버스 정류장 갯수(종점 번호까지 존재), 각 정류장마다 노선 갯수 파악 위해 입력 lst가 주어짐
# -> n 버스노선 갯수
#아이디어
#1. 인덱스 리스트
#2. counts 배열
#3.테스트 케이스 1개이면 2개로 만들기
T = int(input())
for tc in range(1,T+1):
    N = int(input())
    # n개의 노선정보를 모두 읽어놓고 처리 or 읽을때마다 처리
    # 입력이 굉장히 많을 때 한번에 읽어놓은 게 좋겠지만 그럼에도 불구하고 읽을때마다 처리해줘도 괜찮다

    counts  = [0] * 5001 #5000번 정류장까지
    for _ in range(N): #읽을 때마다 처리
        # a -> b 버스 노선의 시점 a와 종점 b, ai <= bi
        A, B = map(int,input().split())

        for i in range(A,B+1):
            counts[i] += 1

    P = int(input()) #노선수를 출력할 p개의 버스 정류장
    #모두 읽어놓고 처리
    busstop = [int(input()) for _ in range(P)]
    print(f'#{tc}', end=' ')

    for j in busstop: #노선 수 출력할 p개의 버스 정류장
        print(counts[j], end=' ')
    print()

 

2. 풍선팡

 

#아이디어
# - 곱하기 전략
di = [0,1,0,-1]
dj = [1,0,-1,0]

T = int(input())
for tc in range(1, T+1):
    N,M = map(int,input().split()) #행열크기
    arr = [list(map(int,input().split())) for _ in range(N)]


    max_v = 0 #꽃가루 최대 합계

    for i in range(N): #터트려볼 풍선의 우치
        for j in range(M):
            cnt = arr[i][j] #터트린 풍선에서 나오는 꽃가루 개수

            for k in range(4): #확인할 방향
                for l in range(1,arr[i][j]+1): #주변방향으로 추가로 터지는 풍선과의 거리

                    ni = i + di[k] * l
                    nj = i + di[k] * l
                    if 0 <= ni <N and 0 <= nj < M:
                        cnt += arr[ni][nj]
            if max_v < cnt:
                max_v = cnt
    print(f'#{tc} {max_v}')

 

3. 재미있는 오셀로 게임

#의문점 : 어떻게 놓는위치마다 대각선,가로,세로를 보지? 게임시작시 정중앙 4칸 배치 어떻게?

# 아이디어 :
# - 돌 놓는 위치가 주어질때, ex. (2,3)은 컴퓨상 (1,2)임임
# - 8개 방향 탐색

def f(i,j,bw,N):
    board[i][j] = bw #지정된 돌 놓기
    for di, dj in [[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0]]:
    ni,nj = i + di, j+ dj
    tmp = [] #뒤집을 돌 인덱스를 저장
    while 0 <= ni < N and 0 <= nj < M and board[ni][nj] ==op[bw]: #반대색 돌이면
        tmp.append((ni,nj)) #뒤집을 돌 저장
        ni,nj = ni + di, nj+ dj #현재 방향으로 계속 이동
    if 0 <= ni < N and 0 <= nj < N and board[ni][nj] == bw:
        for p,q in tmp:
            board[p][q] = bw


#1이면 흑돌,2면 백돌
B = 1 
W = 2
op = [0,2,1]

T = int(input())
for tc in range(1,T+1):
    N,M = map(int,input().split()) #N :보드 한변 길이, M : 돌 놓는 횟수
    play = [list(map(int,input().split())) for _ in range(M)]

    board =[ [0] * N for _ in range(N) ] #N*N board 준비, 0~n-1 인덱스 사용
    #중심부 돌 배치
    # wb
    # bw
    board[N//2-1][N//2-1] = W
    board[N//2-1][N//2] = B
    board[N//2][N//2-1] = W
    board[N//2][N//2] = B

    # 돌 놓기
    for col, row, bw in play: #입력순서 주의
        f(row,col,bw, N)

    bcnt = wcnt = 0
    for i in range(N):
        for j in range(N):
            if board[i][j] == B:
                bcnt += 1
            elif board[i][j] == W:
                wcnt += 1

    print(f'#{tc}')

4. 오목 판정

 

#matrix만들고
# 방향 벡터 5개
# 똑같은 문자 5개 연속이면 가능 출력
di = [0,1, 1, 1]
dj = [1,1,0,-1]

def f(N):
    for i in range(N):
        for j in range(N):

            for k in range(4):
                cnt = 0
                ni,nj = i,j #돌인지 확인할 위치
                while 0 <= ni < N and 0<=nj < N and arr[ni][nj] == 'o':
                    cnt += 1
                    if cnt == '5':
                        return 'YES'

                    ni += dj[k]
                    nj += dj[k]
    return 'N0' #모든 i,j자리에서 모든 방향 k에 대해 살펴보면

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [input() for _ in range(N)]

    ans = f(N)
    print(f'#{tc} {ans}')