글 읽기 - 시간초과 질문 드립니다.

(追記) (追記ここまで)

시간초과 질문 드립니다.

23353번 - 승부 조작

wewd 1년 전 0

방향과 위치정보를 가지고 방문 확인하는 개념으로 접근 해 봤는데 제 생각으론 그렇게까지 계산량이 많지 않을거라 생각했는데 아니었나보네요 ᅲᅲ

다른 방법은 잘 떠오르지 않아 질문 드립니다.

import sys
input = sys.stdin.readline
N = int(input())
board = []
for _ in range(N):
 board.append(list(map(int,input().split())))
# print(board)
move = [(-1,0), (0,1), (1,0), (0,-1), (1,1), (-1,-1), (1,-1), (-1,1)]
visited = [[[0 for _ in range(len(move))] for _ in range(N)] for _ in range(N)]
answer = 0
for i in range(N):
 for j in range(N):
 if board[i][j]==1:
 for k in range(len(move)):
 if visited[i][j][k]==1:
 continue
 dr,dc = move[k]
 cr,cc = i,j
 cscore = 1
 cchange = 1
 visited[i][j][k]=1
 while 1:
 nr,nc = cr+dr,cc+dc
 if 0<=nr<N and 0<=nc<N and board[nr][nc]==1:
 cr,cc = nr,nc
 cscore+=1
 visited[nr][nc][k]=1
 elif 0<=nr<N and 0<=nc<N and board[nr][nc]==2 and cchange==1:
 cr,cc = nr,nc
 cscore+=1
 cchange=0
 visited[nr][nc][k]=1
 else:
 break
 answer = max(answer,cscore)
 if board[i][j]==2:
 for k in range(len(move)):
 if visited[i][j][k]==1:
 continue
 dr,dc = move[k]
 cr,cc = i,j
 cscore = 1
 visited[i][j][k]=1
 while 1:
 nr,nc = cr+dr,cc+dc
 if 0<=nr<N and 0<=nc<N and board[nr][nc]==1:
 cr,cc = nr,nc
 cscore+=1
 visited[nr][nc][k]=1
 else:
 break
 answer = max(answer,cscore)
 
print(answer)

dgddgd 1년 전 1

음. 풀어보고 왔는데 python으로는 쉽지 않네요 좌표를 움직이면서 풀면 시간초과가 뜰 확률이 있어 보입니다.

저는 그냥 6N-2 줄을 전부 검사해서 하나만 바꿨을 때 가장 긴 연속한 1의 개수가 몇 개인지 세는 방향으로 풀었습니다.

얘를 들어서, 예시 상황에 대해 6N-2줄은 다음과 같습니다.

+ dp로 푸는 풀이가 정해같기는 합니다.

입력 : 
5
1 1 0 1 0
1 1 0 0 0
1 0 2 1 0
1 0 2 1 0
0 1 0 0 1
 
체크를 위해 돌아야 할 6N-2개의 줄 :
[1, 1, 0, 1, 0]
[1, 1, 0, 0, 0]
[1, 0, 2, 1, 0]
[1, 0, 2, 1, 0]
[0, 1, 0, 0, 1] # 원래대로 읽기
[1, 1, 1, 1, 0]
[1, 1, 0, 0, 1]
[0, 0, 2, 2, 0]
[1, 0, 1, 1, 0]
[0, 0, 0, 0, 1] # 세로로 읽기
[0]
[1, 0]
[0, 0, 0]
[1, 0, 1, 0]
[1, 1, 2, 1, 1]
[1, 0, 2, 0]
[1, 0, 0]
[1, 1]
[0] # 대각선으로 읽기 : x-y가 같은 것들로
[1]
[1, 1]
[0, 1, 1]
[1, 0, 0, 1]
[0, 0, 2, 0, 0]
[0, 1, 2, 1]
[0, 1, 0]
[0, 0]
[1] # 대각선으로 읽기 : x+y가 같은 것들로

cinador 1년 전 1

1. 질문자님께서 생각하신 8방향 중 4방향만 탐색을 해도 됩니다.

2. visited를 체크 (visited[nr][nc][k] = 1) 하는 조건이 더 필요합니다. 작성하신 코드대로 visited를 체크하게 되면 고려하지 못하는 경우가 있습니다.

이 두 가지를 좀 더 생각해보시면 작성하신 코드에서 조금만 고치면 통과되긴 합니다. 위에 다른 분이 작성하신 답변대로 완전히 다른 방식을 생각해보셔도 됩니다.

wewd 1년 전 0

감사합니다. 힌트 주신걸 기반으로 풀었습니다 ᅲᅲ!

참고로 제가 헤맸던 반례는 아래입니다.

8
0 1 2 1 1 2 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

ans : 5

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

시간초과 질문 드립니다.

wewd 1년 전 0

dgddgd 1년 전 1

cinador 1년 전 1

wewd 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말